洛谷 P2157 [SDOI2009]学校食堂

题意简述

每个人有一个口味，食堂每次只能为一个人做菜

做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为a 异或 b

每个人都有一个容忍度，最多允许紧跟他身后的Bi 个人先拿到饭菜，

求食堂完成所有菜所需的最少时间

题解思路

使用状态压缩。f[i][j][k]表示当前处理第i个人，上一个吃过的人是k，j为第i个人后面7个人的吃饭状态

如果j & 1 == 1，dp[i + 1][j >> 1][k + 7] = minn(dp[i + 1][j >> 1][k + 7], dp[i][j][k + 8]

否则选出i及后面7个人中的一个吃饭，判断一下容忍度

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int C, n, r, ans;

int t[1010], b[1010];

int dp[1010][260][20];

int minn(int &x, int y) {x = min(x, y); }

int calc(int i, int k, int l) {return i + k ? t[i + k] ^ t[i + l] : 0; }

int main()

{

	scanf("%d", &C);

	while (C--)

	{

		ans = INF;

		memset(dp, INF, sizeof(dp));

		scanf("%d", &n);

		dp[1][0][7] = 0;

		for (register int i = 1; i <= n; ++i)

			scanf("%d%d", &t[i], &b[i]);

		for (register int i = 1; i <= n; ++i)

			for (register int j = 0; j < 256; ++j)

				for (register int k = -8; k <= 7; ++k)

					if (dp[i][j][k + 8] != INF)

						if (j & 1) minn(dp[i + 1][j >> 1][k + 7], dp[i][j][k + 8]);

						else

							for (register int l = 0, r = INF; l <= 7; ++l)

								if (!((j >> l) & 1) && i + l <= r)

								{

									minn(r, i + l + b[i + l]);

									minn(dp[i][1 << l | j][l + 8], dp[i][j][k + 8] + calc(i, k, l));

								}

		for (register int i = 0; i <= 8; ++i)

			minn(ans, dp[n + 1][0][i]);

		printf("%d\n", ans);

	}

}