12170−Easy Cimb(DP＋単調なキュー)

2374 ワード
最適化 dp ACM ウバ
この問題はデータ構造でDPを最適化する必要があります.具体的な方法は前の第8章で述べた(データ構造最適化アルゴリズムで紫書P 241)、一つの配列と二つのポインタを使って一つの単調な行列を維持し、O(n)の時間内にスライドウィンドウの最小値を求めることができます.
この最適化があれば、dp[i-1][j](x-d<=j==x+d)の最小値を迅速に求めることができます.
しかし劉汝佳はこのようにしないで、彼はただ1つの指針だけを使って、優先列を守る配列さえ開けていないで、“式を隠します”について最小値を求めました.
具体的なやり方は:
1.まずウィンドウの左端を維持し、ポインタkがウィンドウを超えないようにしてください.x［k］＜x［j］−dであれば、k＋(x配列は大きいから小さいまで順に並べられているので)、右側の境界x［j］＋dを超えないようにして、dp[i]<=dp[i]、[k]なら、k+;.
なぜこのように正しいですか?前に言った優先列とは全然違うようです. 同じ操作です.優先列を守る時はどうやって操作しますか?二つのポインタfront、rearで左境界を更新して、彼が境界を越えることを防止します.一旦超えたらfront+;.そして、新しい値を追加するたびに、現在の列の一番右の要素と新しい値の大きさを見てください.新しい値より大きいなら、rear--、無駄な要素を列に出してください.新しい値より小さいなら、新しい値を入れます.しかし、上の方は同じように、無駄値を削除するというステップを最小値にします.つまりkを更新する時です.
この問題を通じて、優先列に対して区間の最小値を求めるという新たな認識があり、この巧妙な構造方式をより深く理解しました.もう一つの価値があるのは、小さなスライドウィンドウはまだたくさん変形しています.ある時は窓のサイズは可変です.どのように最適化し、どのようにメンテナンスするかは、紫書を通して徐々に体得していきます.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100 + 5;
const int maxx = maxn*maxn*2;
const ll INF = (1ll << 60);
int T,n,d;
ll h[maxn],x[maxx],dp[2][maxx];
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&d);
        for(int i=0;i<n;i++) scanf("%lld",&h[i]);
        if(abs(h[0] - h[n-1]) > (n-1)*d) { //  ，               d
            printf("impossible
"); continue;
        }
        int nx = 0;
        for(int i=0;i<n;i++)
            for(int j=-n+1;j<=n-1;j++)
                x[nx++] = h[i] + j*d; //            ，  、  ，        
        sort(x,x+nx);
        nx = unique(x,x+nx) - x;
        int t = 0;
        for(int i=0;i<=nx;i++) {
            dp[0][i] = INF;
            if(x[i] == h[0]) dp[0][i] = 0; //      
        }
        for(int i=1;i<n;i++) {
            int k = 0;
            for(int j=0;j<nx;j++) {
                while(k < nx && x[k] < x[j]-d) k++;
                while(k+1 < nx && x[k+1] <= x[j]+d && dp[t][k+1] <= dp[t][k]) k++; //              
                if(dp[t][k] == INF) dp[t^1][j] = INF;
                else dp[t^1][j] = dp[t][k] + abs(x[j] - h[i]);
            }
            t ^= 1; //          
        }
        for(int i=0;i<nx;i++)
            if(x[i] == h[n-1])  { printf("%lld
",dp[t][i]); break;  }
    }
    return 0;
}
OpenCVでよく使われるMat、Point、Rectangleなどのデータ構造のまとめ