题解：P13404 [GCJ 2010 #3] Fence

· · 题解

一道非常好的图论，主要是如何转化为最短路。

思路：

拿到题第一眼认为是一个 DP，但 L 的范围可以达到 10^{18}，所以果断思考其它算法。
通过我们惊人的注意力可以发现一个非常简单的贪心：

令 A=\max(B_i)。
我们肯定希望 L 可以表示为 L=q\times A+p 的结构，其中 q=\left \lfloor \frac{L}{A} \right \rfloor ,p=L\bmod A，其中 q\times A 部分用 q 块木板，p 用其它木板。
但这只是理想情况，实际上 p 能用少量木板组成的情况很少，所以如果用其它木板拼出的长度比 q 大，只要模 A 同余即可，多出来的部分可以通过少用几块 A 来补偿。

那么下面就是图论建模：

我们把余数看作图的节点：

为了保证最少木板数，我们定义边权：

现在这就是一个裸的最短路，通过 Dijkstra 可以求出，加堆优化的话时间复杂度近似 O(A\log A)，貌似不加会 TLE。

CODE:

const ll INF=(1LL<<62);
int main() {
    int T=read();
    for(int TTT=1;TTT<=T;TTT++){
        cout<<"Case #"<<TTT<<": ";
        ll L;
        int n;cin>>L>>n;
        vector<int>a(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int A=*max_element(a.begin(),a.end());
        ll p=L/A,q=L%A;
        vector<ll>w(A,INF);
        for(int i=0;i<n;i++){
            ll del=a[i]%A;
            ll wn=A-a[i];
            if(wn<w[del]) w[del]=wn;
        }
        bool flag=false;
        for(int i=0;i<n;i++){
            if(w[i]!=INF){
                flag=true;
                break;
            }
        }
        if(!flag){
            if(q==0) cout<<p<<endl;
            else cout<<"IMPOSSIBLE\n";
            continue;
        }
        vector<ll>dist(A,INF);
        dist[0]=0;
        #define PIIL pair<ll,int>
        priority_queue<PIIL,vector<PIIL>,greater<PIIL>>pq;
        pq.push({0,0});
        while(!pq.empty()){
            ll d=pq.top().first;
            int u=pq.top().second;
            pq.pop();
            if(d!=dist[u]) continue;
            for(int i=0;i<A;i++){
                ll wn=w[i];
                if(wn==INF) continue;
                int v=u+i;
                if(v>=A) v-=A;
                ll nd=d+wn;
                if(nd<dist[v]){
                    dist[v]=nd;
                    pq.push({nd,v});
                }
            }
        }
        if(dist[q]==INF){
            cout<<"IMPOSSIBLE\n";
            continue;
        }
        cout<<p+(dist[q]+q)/A<<endl;
    }
    return 0;
}

在没有卡常的情况下用时 762ms。
那么还是要优化的：

  1. 显然令 g=\gcd(B_1,B_2,\dots,B_n)，若 g\nmid L，那么必定无解；
  2. 模空间压缩：只考虑余数图中能到达的节点。令 G=\gcd(A,\delta_1,\dots,\delta_k)，其中 \delta_i=B_i\bmod A。仅能到达余数为 q 且满足 q\bmod G=0 的节点；并可将模空间从大小 A 压缩为 A' = A/G，将所有 \delta 与目标 q 同除以 G；
  3. 对于小数据可以使用 SPFA，但别忘了大数据它会退化；
  4. Bellman-Ford 也一样；

对于希望抢最优解的非常有用。