题目大意：给定区间内有多少价值可以被凑出来 好题！！！ 如果物品数量可以为负，显然求个就行了 现在物品数量必须非负 任选一个都可以被凑出来 显然如果我们对于每个可以被凑出来，，这个问题就解决了 那么怎么求呢？最短路，使用堆优化Dijkstra即可 时间复杂度
……数据范围错了，
;int n;long long A,B;int a[M];long long f[M];namespace Heap{int heap[M],pos[M],top;void Push_Up(int t){while(t>1){if( f[heap[t]]<f[heap[t>>1]] )swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t>>=1;elsebreak;}}void Insert(int x){heap[++top]=x;pos[x]=top;Push_Up(top);}void Pop(){heap[1]=heap[top–];pos[heap[1]]=1;int t=2;while(t<=top){if( t<top && f[heap[t+1]]<f[heap[t]] )++t;if( f[heap[t]]<f[heap[t>>1]] )swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t<<=1;elsebreak;}}}void Dijkstra(){using namespace Heap;int i;memset(f,0x3f,sizeof f);f[0]=0;for(i=0;i<a[1];i++)Insert(i);while(top){int x=heap[1];Pop();for(i=2;i<=n;i++)if(f[(x+a[i])%a[1]]>f[x]+(x+a[i])/a[1]){f[(x+a[i])%a[1]]=f[x]+(x+a[i])/a[1];Push_Up(pos[(x+a[i])%a[1]]);}}}x){int i;long long re=0;for(i=0;i<a[1];i++)re+=max(0ll,x/a[1]+(x%a[1]>=i)-f[i]);return re;}int main(){int i;cin>>n>>A>>B;for(i=1;i<=n;i++)scanf(“%d”,&a[i]);sort(a+1,a+n+1);swap(a[1],a[n]);if(!a[1])return cout<<0<<endl,0;Dijkstra();cout<<Calculate(B)-Calculate(A-1)<<endl;return 0;}
当你感到悲哀痛苦时，最好是去学些什么东西。
