作法：
當然直接用傳統的無限背包問題建表查詢不會過。
注意到如果 p 可以被湊出來，那麼 p + ci , p + 2*ci , ... 都可以被湊出來，所以如果隨便選定一個 ci (以下叫他 C )，考慮 d[ x ] 是模 C 餘 x 的所有價格中，最小能被湊出來的數字，那麼只要詢問的價錢大於等於這個數字，且和 x 對 C 同餘，那他就可以被湊出來，反之則不行。所以如果有了 d[ i ] 這個陣列那就可以 O(1) 回答每次詢問。
這時就會有類似最短路的模型出現，考慮 d[ x ] 加上其他任意一種幣值 ci ，那麼
d[ (x+ci) % C ] 的候選人又多了一個 d[ x ] + ci ，所以可以看成每個節點 ( 0 ~ C-1 ) 都連出了 n 條邊，且 d[ 0 ] = 0 ，去求 0 到其他所有點的最短路。所以可以用Dijkstra 作，複雜度
O(NClog(NC))，至於 C 因為要取哪個 ci 都可以，所以取最小的 ci 可以加速(很多!!)。
另外還有優化的方法，如果考慮的是： d2[ x ] 為滿足 C * d2[x] + x 是可以被湊出的，模 C = x 的最小價錢(也就等於 d[x] / C ) ( 在我的 code 裡面的 d 其實就是這裡的 d2 )，並且 C 取 ci 之中最大的，那每次鬆弛的時候 d2 最多會增加 1 ( 也就是如果 x 可以走到 y ，那麼這兩個數的 d2 至多差 1 )，所以用一個 deque 作最短路，遇到 d2 多1 的話就加到 deque 的後面，d2 一樣的話就加到 deque 的前面。這就類似傳統的BFS，只是因為BFS的時候每次都是固定增加1，所以擺在 queue 的最後就好，但這時有可能增加 0 ，所以需要一個 deque 把東西加在前面。複雜度降到O(NC)。
但這個優化會慢很多......主要是因為最大的C和最小的C差太多了，在我的電腦上用Dijkstra 作 + 取C是最小的 ci ，跑了30秒多，ZJ上跑了9.8秒，而用 deque 並取C是最大的 ci ，我的電腦跑了 2分半 ......至於把Dijkstra 改成取C是最大的 ci 也跑了3分鐘，比賽的時候如果寫出 deque 作法應該不會過OAO。
用Dijkstra 的 code :
#include<bits/stdc++.h> #define LL long long #define INF 100000000000LL using namespace std; const int maxn=1000000+10 ; struct P { int id ; LL val ; bool operator < (const P &rhs) const { return val>rhs.val ; } }; priority_queue<P> pq ; LL c[60] ; LL d[maxn] ; bool done[maxn] ; main() { int T ; scanf("%d",&T) ; while(T--) { int n,Q ; LL C=INF ; scanf("%d%d",&n,&Q) ; for(int i=1;i<=n;i++) scanf("%lld",&c[i]) , C=min(C,c[i]) ; for(int i=0;i<C;i++) d[i]=INF , done[i]=0 ; d[0]=0 ; while(!pq.empty()) pq.pop() ; pq.push((P){0,0}) ; while(!pq.empty()) { P u=pq.top() ; pq.pop() ; if(done[u.id]) continue ; done[u.id]=1 ; for(int i=1;i<=n;i++) { LL val= u.id+C*d[u.id]+c[i] ; int id=val%C ; if(val/C < d[id]) { d[id]=val/C ; pq.push((P){id,val/C}) ; } } } while(Q--) { LL p ; scanf("%lld",&p) ; if(d[p%C]==INF || (d[p%C]*C+(p%C) > p)) printf("N") ; else printf("Y") ; } printf("\n") ; } }
用 deque 的 code :
#include<bits/stdc++.h> #define LL long long #define INF 100000000000LL using namespace std; const int maxn=1000000+10 ; deque<int> dq ; LL c[60] ; LL d[maxn] ; bool done[maxn] ; main() { int T ; scanf("%d",&T) ; while(T--) { int n,Q ; LL C=-1 ; scanf("%d%d",&n,&Q) ; for(int i=1;i<=n;i++) scanf("%lld",&c[i]) , C=max(C,c[i]) ; for(int i=0;i<C;i++) d[i]=INF , done[i]=0 ; d[0]=0LL ; while(!dq.empty()) dq.pop_front() ; dq.push_front(0) ; while(!dq.empty()) { int u=dq.front() ; dq.pop_front() ; if(done[u]) continue ; done[u]=1 ; for(int i=1;i<=n;i++) { LL val=C*d[u]+u+c[i] ; int id=val%C ; if(d[id] > (val/C)) { d[id]=val/C ; if(val/C > d[u]) dq.push_back(id) ; else dq.push_front(id) ; } } } while(Q--) { LL p ; scanf("%lld",&p) ; if(d[p%C]==INF || (d[p%C]*C+(p%C) > p)) printf("N") ; else printf("Y") ; } printf("\n") ; } }
