原题传送门: P2157 [SDOI2009]学校食堂 https://www.luogu.org/problemnew/show/P2157
一看题目就知道是状压 dp
设 f[i][j][k]表示第 1 到 i-1 个人都吃完了饭, 第 i 个人以及后面的 7 个人是否打饭的状态为 j, 当前最后打饭的人的编号为 i+k(-8<=k<=7)
开始设计状态转移方程
当 j&1 为真, 表示 i 之后的 7 个人中, 不再会有人插队到 i 之前
可得: f[i + 1][j>> 1][k - 1]=Min(f[i + 1][j>> 1][k -1],f[i][j][k])
当 j&1 为假, 可以选 i 和后面 7 个人之一来打饭
枚举 h 从 0 到 7
可得方程: f[i][j | (1 <<h) ][h]=Min(f[i][j | (1 << h) ][h],f[i][j][k] + time(i+k,i+h)
time(i,j)的意义是在第 i 个人之后给第 j 个人打饭所需代价
当然, 这个转移需要考虑到忍耐度的问题. 这样, 在 i 和后面的 7 个人, 不是每一个还未打饭的人都可以先打饭的.
因为编号在他之前的所有未打饭的人的忍耐度必须能忍受这个人在他们之前打饭.
所以, 在这里用了一个变量 x 来统计了一下, 表示到目前为止的未打饭的人的忍受范围 (注意, 不是忍耐度, 忍受范围是指能忍受在其之前打饭的最大位置) 的最小值
对于任何一个人, 如果 i+h>x, 就表示他无法满足编号在他之前的所有人的忍受范围, 就不要考虑这个人了.
状态转移就这么多
最后 ans 是 Min(f[n + 1][0][k]) (-8 <= k <=0 )
- #pragma GCC optimize("O3")
- #include <bits/stdc++.h>
- #define N 1005
- #define inf 0x3f3f3f3f
- using namespace std;
- inline int read()
- {
- register int x=0,f=1;register 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;
- }
- inline int Min(register int a,register int b)
- {
- return a<b?a:b;
- }
- int n,T[N],B[N],f[N][1<<8][20];
- int main()
- {
- int t=read();
- while(t--)
- {
- n=read();
- for(register int i=1;i<=n;++i)
- T[i]=read(),B[i]=read();
- memset(f,inf,sizeof(f));
- f[1][0][7]=0;
- for(register int i=1;i<=n;++i)
- for(register int j=0;j<(1<<8);++j)
- for(register int k=-8;k<=7;++k)
- if(f[i][j][k+8]!=inf)
- {
- if(j&1)
- f[i+1][j>>1][k+7]=Min(f[i+1][j>>1][k+7],f[i][j][k+8]);
- else
- {
- int x=inf;
- for(register int h=0;h<=7;++h)
- if(!((j>>h)&1))
- {
- if(i+h>x)
- break;
- x=Min(x,i+h+B[i+h]);
- f[i][j|(1<<h)][h+8]=Min(f[i][j|(1<<h)][h+8],f[i][j][k+8]+(i+k?(T[i+k]^T[i+h]):0));
- }
- }
- }
- int ans=inf;
- for(register int k=0;k<=8;++k)
- ans=Min(ans,f[n+1][0][k]);
- printf("%d\n",ans);
- }
- return 0;
- }
[题解] Luogu P2157 [SDOI2009]学校食堂
来源: http://www.bubuko.com/infodetail-2794514.html