3521.【NOIP 2013シミュレーション11.7 B組】道路カバー
Description
Arでこぼこした道を高さの異なるN段に分け,i段目の高さをH[i]で表す.現在,Tarは全部でn種の土が利用可能であり,それらは所与の連続k個の部分を覆うことができる.i番目の土壌については,C[i]の価格で区間[i,min(n,i+k−1)]の区間の高さをE[i]増加させることができる.Tarは、いくつかの土を使用した後、この道の最低の高さができるだけ高くなるように、土の使用計画を設定し、この計画は以下の2つの要求を満たさなければならない:(1)各土は1回しか使用できない.(2)泥の使用コストはM以下でなければならない.この最低の高さがどれくらい高いかを要求します.
Input
第1の挙動は、N,M,Kの3つの正の整数である.次に、N行毎に、上記のような正の整数H[i],E[i],C[i]を3つずつ行う.
Output
最下部の高さの最大値として、数値が1つしか出力されません.
Sample Input
4 20 1
1 3 5
1 7 3
4 6 9
3 5 13
Sample Output
3
Data Constraint
30%のデータに対して:N≦20.100%のデータについて:1≦K≦11,1≦N≦100,0≦M,H[i],E[i],C[i]≦1000000であった.
Solution
二分+状態圧縮DP:
二分列挙最低の高さ(Mとする)は、次に、f[i][j]を最後までi位、前k位(iを含む)を選択または選択しない状態をjとする最小金銭的代価とすると判断することを考慮し、状態xがf[n][x]≦Mである限り、この高度が合法であることを説明する.注意1ビットiはその前kビットのみから得られるので、f[i][j]はその前kビットから得られるので、jが表す状態はkビットのみである.kの範囲は極めて小さいのでタイムアウトしません.次に状態の遷移を考える:まず,jという状態がi+1の前のk位,すなわちiの前のk-1位とiであるため,i+1位に影響を及ぼすのはこれらの点だけであるため,jの状態を列挙し,各状態で選択される点のi+1高さへの寄与と求め,直前のk位で選択された土のeを求める.[i]と統計をとると、2つの状況が移行します.
第1種:第i+1位不選:f[i+1][第i+1位不選の状態]=min(f[i+1][第i+1位不選の状態],f[i][j]);
第2種:第i+1位選択:f[i+1][第i+1位選択の状態]=min(f[i+1][第i+1位選択の状態]、f[i][j]+この土を選択する費用);
いずれの転移も、選択または非選択後のi+1番目の土壌の高さが現在のMより大きいことを満たすことに注意されたい.
Code1
Code2
作者:zsjzliziyang QQ:1634151125転載と修正本文の住所を明記してください:https://blog.csdn.net/zsjzliziyang/article/details/83272408
Arでこぼこした道を高さの異なるN段に分け,i段目の高さをH[i]で表す.現在,Tarは全部でn種の土が利用可能であり,それらは所与の連続k個の部分を覆うことができる.i番目の土壌については,C[i]の価格で区間[i,min(n,i+k−1)]の区間の高さをE[i]増加させることができる.Tarは、いくつかの土を使用した後、この道の最低の高さができるだけ高くなるように、土の使用計画を設定し、この計画は以下の2つの要求を満たさなければならない:(1)各土は1回しか使用できない.(2)泥の使用コストはM以下でなければならない.この最低の高さがどれくらい高いかを要求します.
Input
第1の挙動は、N,M,Kの3つの正の整数である.次に、N行毎に、上記のような正の整数H[i],E[i],C[i]を3つずつ行う.
Output
最下部の高さの最大値として、数値が1つしか出力されません.
Sample Input
4 20 1
1 3 5
1 7 3
4 6 9
3 5 13
Sample Output
3
Data Constraint
30%のデータに対して:N≦20.100%のデータについて:1≦K≦11,1≦N≦100,0≦M,H[i],E[i],C[i]≦1000000であった.
Solution
二分+状態圧縮DP:
二分列挙最低の高さ(Mとする)は、次に、f[i][j]を最後までi位、前k位(iを含む)を選択または選択しない状態をjとする最小金銭的代価とすると判断することを考慮し、状態xがf[n][x]≦Mである限り、この高度が合法であることを説明する.注意1ビットiはその前kビットのみから得られるので、f[i][j]はその前kビットから得られるので、jが表す状態はkビットのみである.kの範囲は極めて小さいのでタイムアウトしません.次に状態の遷移を考える:まず,jという状態がi+1の前のk位,すなわちiの前のk-1位とiであるため,i+1位に影響を及ぼすのはこれらの点だけであるため,jの状態を列挙し,各状態で選択される点のi+1高さへの寄与と求め,直前のk位で選択された土のeを求める.[i]と統計をとると、2つの状況が移行します.
第1種:第i+1位不選:f[i+1][第i+1位不選の状態]=min(f[i+1][第i+1位不選の状態],f[i][j]);
第2種:第i+1位選択:f[i+1][第i+1位選択の状態]=min(f[i+1][第i+1位選択の状態]、f[i][j]+この土を選択する費用);
いずれの転移も、選択または非選択後のi+1番目の土壌の高さが現在のMより大きいことを満たすことに注意されたい.
Code1
#include
#include
#include
#include
#define N 120
using namespace std;
int l,r,mid,ans,n,m,k,s,x,a,h[N],e[N],c[N],f[N][1<<12];
int dp(int x){
memset(f,127,sizeof(f));
f[0][0]=0;
for(int i=0;i<=n-1;i++){
for(int j=0;j<=(1<>=1;}
if(s+h[i+1]>=x) f[i+1][(j<<1)&((1<=x) f[i+1][((j<<1)+1)&((1<>1;
if(dp(mid)){ans=mid;l=mid+1;}
else{r=mid-1;}
}
printf("%d
",ans);
return 0;
} Code2
#include
#include
#include
using namespace std;
int n,m,k,e[200],h[200],c[200],f[200][5000],l,r,ans,mid,i;
bool dp(int x){
memset(f,127,sizeof(f));
f[0][0]=0;
int i,j,l,sum;
for (i=0;i0;l--)
if ((1<=x)
f[i+1][j>>1]=min(f[i+1][j>>1],f[i][j]);
if (sum+h[i+1]+e[i+1]>=x)
f[i+1][(j>>1)|(1<>1)|(1< 作者:zsjzliziyang QQ:1634151125転載と修正本文の住所を明記してください:https://blog.csdn.net/zsjzliziyang/article/details/83272408