DP(状压进阶一)

写在前面: 本题很有难度, 是dp里面较难的类型, 先贴一波大佬的博客

我是传送门

题意 : 小F 的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。 由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为（a or b）-（a and b），而做第一道菜是不需要计算时间的。其中，or 和and 表示整数逐位或运算及逐位与运算，C语言中对应的运算符为“|”和“&”。学生数目相对于这个学校还是比较多的，吃饭做菜往往就会花去不少时间。因此，学校食堂偶尔会不按照大家的排队顺序做菜，以缩短总的进餐时间。虽然同学们能够理解学校食堂的这种做法，不过每个同学还是有一定容忍度的。也就是说，队伍中的第i 个同学，最多允许紧跟他身后的Bi 个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭，当前同学将会十分愤怒。因此，食堂做菜还得照顾到同学们的情绪。 现在，小F 想知道在满足所有人的容忍度这一前提下，自己的学校食堂做完这些菜最少需要多少时间。

>> face <<

Strategy:状压

状态: dp[i][j][k]->搞完前i-1个人,第i个人以及其后面七个人的状态为j,且上一个打饭的人编号为i+k的情况的最小时间 (请仔细思考一下k的取值范围)

目标: $dp[n+1][0][j\in[0,8]]\mid _{min}$dp[n+1][0][j∈[0,8]]∣min​

边界: dp[1][0][id(-1)] = 0; 其中id代表一种偏移量

合法判断: 无

转移方程: 当$j\&amp;1$j&1为真，就表示第$i$i个人已经打完饭,$i$i之后的$7$7个人中，还没打饭的人就再也不会插入到第$i$i个人前面了。所以这时候可以转移到 $dp[i+1][j&gt;&gt;1][k−1]$dp[i+1][j>>1][k−1],即$dp[i+1][j&gt;&gt;1][k−1]=min(dp[i+1][j&gt;&gt;1][k−1],dp[i][j][k])$dp[i+1][j>>1][k−1]=min(dp[i+1][j>>1][k−1],dp[i][j][k]),不需要累积时间（因为在$j\&amp;1$j&1为真的情况下，$dp[i][j][k]$dp[i][j][k]和$dp[i+1][j&gt;&gt;1][k−1]$dp[i+1][j>>1][k−1]的意义是一样的）。

而为什么意义是一样的呢？因为可以看出，最后一个打饭的人的编号为$(i+1)+(k-1)=i+k(i+1)+(k−1)=i+k$(i+1)+(k−1)=i+k(i+1)+(k−1)=i+k，和$dp[i][j][k]$dp[i][j][k]表示的一样。而第$i$i个人也打完了饭，所以满足「第1个人到第$i$i个人已经打完饭」这个条件。而$j&gt;&gt;1$j>>1就是说$i$i之后的第$1$1个人就是$i+1$i+1之后的第$0$0个人（就是$i+1$i+1本人），$i$i之后的第2个人就是$i+1$i+1之后的第$1$1个人，$i$i之后的第$3$3个人就是$i+1$i+1之后的第$2$2个人，…。这样就可以看出意义一样了。

当$j\&amp;1$j&1为假时，是没办法转移到$dp[i+1]$dp[i+1]的（因为$i+1$i+1之前的人还有$i$i没有打完饭）。但是这时候可以把$i$i以及$i$i之后的7个人中选出一个人打饭，也就是枚举h从0到7，$dp[i][j|(1&lt;&lt;h)][h]=min(dp[i][j|(1&lt;&lt;h)][h],dp[i][j][k]+time(i+k,i+h))$dp[i][j∣(1<<h)][h]=min(dp[i][j∣(1<<h)][h],dp[i][j][k]+time(i+k,i+h)),其中$time(i,j)$time(i,j)表示如果上一个人编号为$i$i，当前的人编号为$j$j，那么做编号为$j$j的人的菜需要的时间。 当然，这个转移需要考虑到忍耐度的问题。这样，在$i$i和$i$i之后的7个人，不是每一个还未打饭的人都可以先打饭的。因为编号在他之前的所有未打饭的人的忍耐度必须能忍受这个人在他们之前打饭。所以，在这里用了一个变量$r$r来统计了一下，表示到目前为止的未打饭的人的忍受范围（注意，不是忍耐度，忍受范围是指能忍受在其之前打饭的最大位置）的最小值，对于任何一个人，如果$i+h&gt;ri+h&gt;r$i+h>ri+h>r，就表示他无法满足编号在他之前的所有人的忍受范围，就不要考虑这个人了。

attention: 转移缜密

双倍经验: 转移方程巧妙,状态新颖

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define db double
#define oo 0x3f3f3f3f
#define eps 0.00001
#define all(x) x.begin(), x.end()
#define met(a, b) memset(a, b, sizeof(a))
#define id(x) ((x + 8))
#define bin(x) cerr << #x << " is " << bitset<8>(x) << endl
#define what_is(x) cerr << #x << " is " << x << endl
#define lowbit(x) x &(-x)
using namespace std;
const int maxn = 1002;
const int mod = 9999973;

int dp[maxn][1 << 8][20], t[maxn], b[maxn];
int main()
{
	ios::sync_with_stdio(0);
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		_rep(i, 1, n) cin >> t[i] >> b[i];
		memset(dp, oo, sizeof(dp));
		t[0] = b[0] = 0;
		dp[1][0][id(-1)] = 0; // -1 + 1 = 0, 弄完第i-1行最后一个是0
		_rep(i, 1, n)
		{
			_rep(j, 0, (1 << 8) - 1)
			{
				_rep(k, -8, 7)
				{
					//what_is(i), bin(j), what_is(k), what_is(id(k));
					if (dp[i][j][id(k)] == oo)
						continue;
					if (j & 1)
						dp[i + 1][j >> 1][id(k - 1)] = min(dp[i + 1][j >> 1][id(k - 1)], dp[i][j][id(k)]);
					else
					{
						int R = oo;
						_rep(h, 0, 7)
						{
							if (i + h > R)
								break;
							if(j >> h & 1)continue;
							R = min(R, i + h + b[i + h]);
							dp[i][j | 1 << h][id(h)] = min(dp[i][j | 1 << h][id(h)], dp[i][j][id(k)] + (i + k ? t[i + k] ^ t[i + h] : 0));
						}
					}
				}
			}
		}
		int ans = oo;
		_rep(k, 0, 8)
		{
			ans = min(dp[n + 1][0][k], ans);
		}
		cout << ans << endl;
	}
}