题目链接
题目大意：给定n个物品，每个物品有一个非负价值，问[L,R]区间内有多少价值可以被凑出来
题解：先用前缀和转化一下问题，变成求 [0,X] 内能凑出的数
如果物品数量可以为负，求个gcd就可以了
现在物品数字非负 令mn=min(a[i]),若x能被凑出，则x+mn可被凑出
建mn个点，dis[i]表示满足x mod mn = i的最小的x 考虑加入物品a[i]，假设已经有d[u]，那么可以从d[u]转移到d[(u+a[i]) mod mn]，代价为a[i] 这样就可以用最短路做了
mn取最小的a[i]是为了让点数最少，mn取大一些对正确性没有影响
详细版
我的收获：模型强啊，跪啊
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define M 500010 #define INF 1e60 #define pii pair<long long,int> int n,m,mn,t,head[M],a[20]; long long L,R,dis[M]; bool vis[M]; struct edge{int to,val,nex;}e[M*20]; priority_queue<pii,vector<pii>,greater<pii> > q; void add(int u,int v,int z){e[t]=(edge){v,z,head[u]};head[u]=t++;} void dijkstra() { memset(vis,0,sizeof(vis)); for(int i=0;i<mn;i++) dis[i]=INF; dis[0]=0;q.push(make_pair(0,0)); while(!q.empty()) { int u=q.top().second;q.pop(); if(vis[u]) continue;vis[u]=1; for(int i=head[u];i!=-1;i=e[i].nex){ int v=e[i].to; if(dis[v]>dis[u]+e[i].val) dis[v]=dis[u]+e[i].val,q.push(make_pair(dis[v],v)); } } } long long cal(long long x) { long long ans=0; for(int i=0;i<mn;i++) if(dis[i]<=x) ans+=(x-dis[i])/mn+1;//计算有多少个k满足k*mn+i<=x，因为k>=0,所以还要加1 return ans; } void work() { dijkstra(); cout<<cal(R)-cal(L-1)<<endl; } void init() { t=0;memset(head,-1,sizeof(head)); cin>>n>>L>>R;mn=INF; for(int i=1;i<=n;i++) scanf("%d",&a[i]),mn=min(mn,a[i]); for(int i=0;i<mn;i++) for(int j=1;j<=n;j++) if(a[j]%mn!=0) add(i,(i+a[j])%mn,a[j]); } int main() { init(); work(); return 0; }“`
