[ZJ b384][NPSC 2014] H. H Game

這題是我看官方的解+問人才會的，這解太神啦!!

作法：

當然直接用傳統的無限背包問題建表查詢不會過。

注意到如果 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") ;
    }
}