DP----cf#336 div2 C D
6341 ワード
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爆発した灯台数
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;i
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;i
int 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;
}