状压DP
f(i,j,k)表示前i−1个人已经吃了饭，且在i之后的状态为j的人也吃了饭（用二进制表示后面的状态），最后吃的那个人是i之后的第k个
（注意k可以是负数）
然后
如果j&1=1那么就表明第i个人也是吃了的，所以可以转移到f(i+1,j>>1,k−1)
否则就枚举下一个吃饭的人，转移到f(i,j+1<<l,l)
这么看也不是很难吧哈。。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-9 # define MOD 1000000000 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r //# define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void Out(int a) { if(a<0) {putchar('-'); a=-a;} if(a>=10) Out(a/10); putchar(a%10+'0'); } const int N=1005; //Code begin... struct Node{int t, b;}node[N]; int dp[N][1<<8][20]; int main () { int T, n; scanf("%d",&T); while (T--) { scanf("%d",&n); FO(i,0,N) FO(j,0,1<<8) FO(k,0,20) dp[i][j][k]=INF; FOR(i,1,n) scanf("%d%d",&node[i].t,&node[i].b); int mi=INF; FOR(i,1,n) { --mi; if (mi<0) break; mi=min(mi,node[i].b); dp[1][1<<(i-1)][(i-1)+8]=0; } FOR(i,1,n) FO(j,0,1<<8) FOR(k,0,15) { if (dp[i][j][k]==INF) continue; if (j&1) dp[i+1][j>>1][k-1]=min(dp[i+1][j>>1][k-1],dp[i][j][k]); else { mi=INF; FOR(l,i,n) { --mi; if (mi<0) break; if ((j&(1<<(l-i)))==0) { dp[i][j|(1<<(l-i))][l-i+8]=min(dp[i][j|(1<<(l-i))][l-i+8],dp[i][j][k]+(node[l].t^node[i+k-8].t)); mi=min(mi,node[l].b); } } } } int ans=INF; FOR(i,0,15) ans=min(ans,dp[n+1][0][i]); printf("%d ",ans); } return 0; }