题意：
有点复杂，自行浏览吧 题目链接
分析：
我们发现DP转移时需要记录以下几个信息：
打饭队列的队首是谁，上一个打饭的是谁，队列前
b
[
i
]
b[i]
b[i]个人的状态
然后我们根据这些信息设立DP状态，记
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k]表示该第
i
i
i个人打饭（等价于前
i
−
1
i-1
i−1个人已经买完饭）此时队列前7个人的状态是
j
j
j，上一个打饭的人是
i
+
k
i+k
i+k。由于打饭的人在
i
i
i的前后都可以，所以
k
k
k的范围就是
[
−
8
,
8
]
[-8,8]
[−8,8]，加上偏移量就是
[
0
,
16
]
[0,16]
[0,16]
接下来我们考虑转移，分为两种情况：
第
i
i
i个人已经买完饭了，也就是说直接将状态转移到
i
+
1
i+1
i+1就可以了
f
[i
+1][j
>>1][k
-1]=min(f
[i
+1][j
>>1][k
-1],f
[i
][j
][k
]);
第
i
i
i个人还没有买饭，那就在所有人都能忍受的范围内枚举买饭的人是谁
f
[i
][j
|(1<<l
)][l
]=min(f
[i
][j
|(1<<l
)][l
],f
[i
][j
][k
]+(t
[i
+k
]^t
[i
+l
]));
状态初始化为
f
[
1
]
[
0
]
[
7
]
f[1][0][7]
f[1][0][7]表示该第
1
1
1个人买饭，此时身后所有人都没有买完，上一个买的人是第
7
−
8
7-8
7−8个，最后统计枚举
i
i
i然后取
f
[
n
+
1
]
[
0
]
[
i
]
f[n+1][0][i]
f[n+1][0][i]的最小值
代码：
#include<bits/stdc++.h>
using namespace std
;
namespace zzc
{
const int maxn
= 1005;
int f
[maxn
][256][20],b
[maxn
],t
[maxn
];
int T
,n
;
void work()
{
scanf("%d",&T
);
while(T
--)
{
memset(f
,0x3f,sizeof(f
));
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++) scanf("%d%d",&t
[i
],&b
[i
]);
f
[1][0][7]=0;
for(int i
=1;i
<=n
;i
++)
{
for(int j
=0;j
<(1<<8);j
++)
{
for(int k
=-8;k
<=7;k
++)
{
if(f
[i
][j
][k
+8]!=0x3f3f3f)
{
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 lim
=0x3f3f3f;
for(int l
=0;l
<=7;l
++)
{
if(!((j
>>l
)&1))
{
if(i
+l
>lim
) break;
lim
=min(lim
,i
+l
+b
[i
+l
]);
f
[i
][j
|(1<<l
)][l
+8]=min(f
[i
][j
|(1<<l
)][l
+8],f
[i
][j
][k
+8]+(i
+k
?t
[i
+k
]^t
[i
+l
]:0));
}
}
}
}
}
}
}
int ans
=0x3f3f3f;
for(int i
=0;i
<=8;i
++) ans
=min(ans
,f
[n
+1][0][i
]);
printf("%d\n",ans
);
}
}
}
int main()
{
zzc
::work();
return 0;
}
