http://www.lydsy.com/JudgeOnline/problem.php?id=1226
关键点：一个人只能忍受 ‘紧跟’ 在他 后面的b个人比他先打到饭
dp[i][j][k] 前i-1个人已经打完了饭，第i个人和他后面的7个人 是否打上饭的状态为j，当前最后一个已经打到饭的人是k
b至多只有7，所以k可以修改为 当前最后一个已经打到饭的人与i的位置关系为k，k∈[-8,7]
转移：
若j&1 == true，说明 第i个人已经打上了饭，那么 推移到下一个人 即可 dp[i+1][j>>1][k-1] = min (dp[i+1][j>>1][k-1],dp[i][j][k])
否则， 枚举 谁打饭，dp[i][j|1<<h][k+h]=min( dp[i][j|1<<h][k+h] , dp[i][j][k]+cost(i+k,i+h))
注意在枚举的过程中，时刻要保证当前枚举的人 在前面没有打饭的人的忍耐度 之内
还有第1个打饭的人不需要时间，所以初始时时 dp[1][0][-1]=0，其余dp[i][j][k]=inf
这样当i+k=0 时，前一个打饭的是第0个人，那么现在打饭的就是第一个人
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; #define N 1003
const int M=<<; int t[N],b[N]; int dp[N][M+][]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int cost(int i,int j)
{
if(!i) return ;
return (t[i]|t[j])-(t[i]&t[j]);
} inline void min(int &i,int j)
{
i=j<i ? j : i;
} int main()
{
int T,n,inf,lim,ans;
read(T);
while(T--)
{
read(n);
for(int i=;i<=n;++i)
{
read(t[i]); read(b[i]);
min(b[i],n-i);
}
memset(dp,,sizeof(dp));
inf=dp[][][];
dp[][][-+]=;
for(int i=;i<=n;++i)
for(int j=;j<M;++j)
for(int k=-;k<=;++k)
if(dp[i][j][k+]!=inf)
if(j&) min(dp[i+][j>>][k-+],dp[i][j][k+]);
else
{
lim=b[i];
for(int h=;h<=lim;++h)
if(!(<<h&j))
{
min(dp[i][j|<<h][h+],dp[i][j][k+]+cost(i+k,i+h));
min(lim,h+b[i+h]);
}
}
int ans=inf;
for(int i=-;i<=-;++i) min(ans,dp[n+][][i+]);
printf("%d\n",ans);
}
}