省選専練【SDOI 2009】学校食堂

状圧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の人による.

#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