省選専練【SDOI 2009】学校食堂
1445 ワード
状圧DP
なぜ状圧DPなのか
‘100%のデータに対して,1≦N≦1000,0≦Ti≦1000,0≦Bi≦7,1≦C≦5を満たす.’
許容度が超小さい.
これにより、各次元の許容度の状態を列挙することができる.
f(i,j,k)はi-1個がセットされていることを示す
i-i+7個目の状態はj
前回料理を買ったのは現在のkの人による.
なぜ状圧DPなのか
‘100%のデータに対して,1≦N≦1000,0≦Ti≦1000,0≦Bi≦7,1≦C≦5を満たす.’
許容度が超小さい.
これにより、各次元の許容度の状態を列挙することができる.
f(i,j,k)はi-1個がセットされていることを示す
i-i+7個目の状態はj
前回料理を買ったのは現在のkの人による.
#include
#include
#include
#include
#include
using namespace std;
const int INF=0x3f3f3f3f;
int w[10];
int dp[1200][1<<8][18];
int t[1200];
int b[1200];
#define f(i,j,k) dp[i][j][k+10]
int n;
int Calc(int x,int y){
if(!x)
return 0;
return (t[x] | t[y])-(t[x] & t[y]);
}
int main(){
int T;
scanf("%d",&T);
w[0]=1;
for(int i=1;i<=9;i++){
w[i]=w[i-1]<<1;
}
while(T--){
// memset(T,0,sizeof(T));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&t[i]);
scanf("%d",&b[i]);
}
for(int i=0;i<=n+1;i++){
for(int j=0;j>1,k-1)=min(f(i+1,j>>1,k-1),f(i,j,k));
else{
int r=INF;
for(int l=0;l<=7;l++){
if((j&w[l])==0){
if(i+l>r)
break;
r=min(r,i+l+b[i+l]);
f(i,j|w[l],l)=min(f(i,j|w[l],l),f(i,j,k)+Calc(i+k,i+l));
}
}
}
}
}
}
}
/*for(int i=1;i<=n;i++){
for(int j=0;j