题目大意
小F 的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味都可以用一个非负整数表示。 由于人手不够，食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的，若前一道菜的对应的口味是a，这一道为b，则做这道菜所需的时间为（a or b）-（a and b），而做第一道菜是不需要计算时间的。其中，or 和and 表示整数逐位或运算及逐位与运算，C语言中对应的运算符为“|”和“&”。学生数目相对于这个学校还是比较多的，吃饭做菜往往就会花去不少时间。因此，学校食堂偶尔会不按照大家的排队顺序做菜，以缩短总的进餐时间。虽然同学们能够理解学校食堂的这种做法，不过每个同学还是有一定容忍度的。也就是说，队伍中的第i 个同学，最多允许紧跟他身后的Bi 个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭，当前同学将会十分愤怒。因此，食堂做菜还得照顾到同学们的情绪。 现在，小F 想知道在满足所有人的容忍度这一前提下，自己的学校食堂做完这些菜最少需要多少时间。对于100%的数据，满足1 ≤ N ≤ 1,000，0 ≤ Ti ≤ 1,000，0 ≤ Bi ≤ 7，1 ≤ C ≤ 5。
题解
审题
题目的要求不是让你求出一个学生的排列，这么理解题意是错误的。正确理解题意是在原来的排列的基础上一个一个同学出队去打饭。
状态的设计
首先，我们看到0 ≤ Bi ≤ 7，这意味着对于一个人x，如果他开始打饭了，那么[1, x-7]的人肯定都已经打完饭了。所以我们令i=x-7，表示[1, i-1]的人都打完饭这一限制条件。因为食物的美味度与前一个打饭的人有关，所以我们用k表示前一个人打饭相对于i的位置偏右了多少（$-8\leq k\leq 7$）。因为同学们的有各自的容忍度，下一个打饭的人的取值范围受到了[i, i+7]内同学的具体状态的影响，所以我们要用S来表示[i, i+7]内同学的具体打饭状态。f表示最短时间。这样，f(i, S, k)就诞生了。
状态的转移
如果S表示第i位同学打完饭了，那么状态可以转移到f(i + 1, S >> 1, k - 1)；否则，从前往后枚举[i, i+7]内没有打饭的人，边枚举边更新可选打饭人的取值范围，因为下一个打饭人要符合他前面所有人的容忍度，而不仅仅是第i个。有Update(f(i, S | (1 << j), j)) with delta(i + k, i + j)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; //#define Update(x, y) (x) = min((x), (y))
const int MAX_PERSON = 1010, MAX_STATE = 1 << 8, MAX_LAST = 20, INF = 0x3f3f3f3f;
int Dp[MAX_PERSON][MAX_STATE][MAX_LAST];
#define F(i, S, k) Dp[i][S][(k) + 8] void Update(int &x, int y)
{
x = min(x, y);
} struct Person
{
int AfterIdLimit, A;
}_persons[MAX_PERSON];
int TotPerson; int DP()
{
memset(Dp, INF, sizeof(Dp));
F(1, 0, -1) = 0;
for (int i = 1; i <= TotPerson; i++)
for (int S = 0; S <= (1 << 8) - 1; S++)
for (int k = -8; k <= 7; k++)
{
if (F(i, S, k) >= INF)
continue;
_printf("F(%d, %d, %d) = %d\n", i, S, k, F(i, S, k));
if (S & 1)
{
if (k >= -8)
Update(F(i + 1, S >> 1, k - 1), F(i, S, k));
}
else
{
int afterLimit = INF;
for (int j = 0; j <= 7; j++)
{
if (!((S >> j) & 1))
{
if (i + j > afterLimit)
break;
Update(afterLimit, i + j + _persons[i + j].AfterIdLimit);
Update(F(i, S | (1 << j), j), F(i, S, k) + (i + k ? (_persons[i + k].A ^ _persons[i + j].A) : 0));
}
}
}
}
int ans = INF;
for (int k = -8; k <= 0; k++)
Update(ans, F(TotPerson + 1, 0, k));
return ans;
} int main()
{
int caseCnt;
scanf("%d", &caseCnt);
while (caseCnt--)
{
scanf("%d", &TotPerson);
for (int i = 1; i <= TotPerson; i++)
scanf("%d%d", &_persons[i].A, &_persons[i].AfterIdLimit);
printf("%d\n", DP());
}
return 0;
}