DP----cf#336 div2 C D

http://codeforces.com/contest/608/problem/D
2016-5-9考え方:C、テーマについてはまずアルゴリズムを考えない:暴力的な考えはn*nで、灯台ごとに私は何個が爆破されたT(つまり何個が活性化された)があるかをシミュレートして、最小の爆破を選ぶのは最も活性化されたのです!まず1つの配列をすべて0に初期化し、for(int i=n;i>=1;i-)を設定し、各灯台について、後ろからこの場所で爆発した最も少ない灯台num 1を記録し、それを活性化してどれだけの灯台num 2を爆破したかを計算し、爆発範囲外の最初の灯台を更新し、この灯台を示す考えがある.かもしれない!の最小値はNum 1+num 2、すなわちdp[j]=min(dp[j],num 1+num 2)である.そしてdp[1]まで更新すると、最も爆破された灯台数が得られる.具体的にはどうでもいいですが、このような考えは必然的に実行できると思います.问题を见て、1つの条件が役に立たないことを発见します:右侧で1つの任意の位置の任意の爆発のT活动(潜せりふは:任意の灯台を选んで活性化を始めることができます)を选ぶことができて、だから私达は初期化して0になることができなくて、iに対して、初期は(i+1-nの灯台はすべて爆破します)、よし、理论acは完成します
D:題意:1つの列に対して、毎回回文列を破壊することができて、少なくとも何歩で全体の列を破壊することができて、祖玛のゲームです.ちょっと難しいですが、ハハ区間dp;
やらないやらないやらないやら、dpが強くなってから振り返ってみよう
一人で実験室でやったこの試合は、前の2つの問題の小さな間違いに長い間引っかかっていて、2つの問題を水に流してしまった.C:つまり、nつの塔があり、それぞれの塔には爆発範囲のpowerがあり、右から左に灯台を活性化し、灯台を活性化すると、power範囲の灯台を爆破し、次の灯台を活性化します.右側に任意の位置のPowerの灯台を挿入して、最も小さい爆破された灯台の数を求めることができます.dp[i]は、灯台iをアクティブにすると、dp[i]個の灯台を破壊することを表す.このようにして,状態遷移方程式は,>=pos[i]−power[i]の最初の灯台=pposを二分でシーケンス中に見つけることができる.dp[i]=dp[ppos-1]+(i-ppos)/前の爆発数+i爆発した灯台数

//     
pair<int,int> p[1000005];
int dp[1000005];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        scanf("%d %d",&p[i].first,&p[i].second);
    sort(p,p+n);  //  ，      dp  
    int ans;
    for (int i=0;i<n;i++){
        int pp=lower_bound(p,p+n,make_pair(p[i].first-p[i].second,-1))-p;
        //            
        dp[i]=dp[pp-1]+i-pp;  //i-pp    i      
        ans=min(ans,n-i-1+dp[i]);
    }
    cout<<ans;
}

D題——-も1つのdpが最初に1次元のdpを考えて、2つのdp[n]を設定しました.しかし、脳の容量が足りず、良いものは思いつかなかった.iに対して0-iからアドレスposを探して、返信文を形成したいのでdp[i]=dp[pos-1]+1;しかしながら、第3の群のサンプルでは、144,232 1"232"が中間に挟まれ、dp[n−1]がpos=0と返信できない.条件はnum[i]=num[pos]でdp状態の移行を開始できるはずだと考え始めたが、当時は思考が1次元に限られていて、半日は卵の役に立たないと思っていた.最后にやはり他の人のコードを见て、他の人が2次元を使うことを见ていくつか理解しました.
dp[i][j]はiからjの範囲内で最小のステップ数を表すnum[i]=num[j]であれば比較的容易に考えられる:dp[l][r]=dp[l+1][k-1]+dp[k+1][r]そこで考えられる:まずdp[i][i]からdp[i][i+1]からdp[i][i+1]まで順次左から右への更新
だから最初はfor(int i=0;iint num[505]; int dp[505][505]; int main() { freopen("1.txt","r",stdin); int n; while(~scanf("%d",&n)){ for(int i=0;i<n;i++) scanf("%d",&num[i]); //mem(dp); int l,r; for(int i=0;i<n;i++) dp[i][i]=1; // 0 n —— n ， // 0-1 1-2 2-3 3-4 ... // 0-2 1-3 2-5... // 0-n-1 for(int i=0;i<n;i++) for(int j=0;j<n-i;j++){ //j<n-j r<n l=j; r=i+j; if (l==r) continue; dp[l][r]=dp[l+1][r]+1; // dp[l][r]=dp[l][r-1]+1; ， for(int k=l+1;k<=r;k++){ if(num[l]==num[k]){ if(k==l+1) dp[l][r]=min(dp[l][r],1+dp[k+1][r]); else dp[l][r]=min(dp[l][r],dp[l+1][k-1]+dp[k+1][r]); } } } printf("%d
",dp[0][n-1]); } return 0; }