P5322 BJOI2019 排兵布阵

基本思路

一眼背包，然后无脑套01，样例也过了，直接提交，40pts。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int M = 50010;
int s, n, m;
int F[M];
int w;

int main()
{
	cin >> s >> n >> m;
	for (int i = 1; i <= s; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> w;
			for (int k = m; k >= w * 2 + 1; k--)
			{
				F[k] = max(F[k], F[k - w * 2 - 1] + j);
			}
		}
	}
	cout << F[m];
	return 0;
}

改进思路

状态转移方程出问题

如果击败一个更多士兵的对手，比他士兵少的对手本应是一并击败并得分的，但我的方程只能计算击败的一个对手的分数。

理解上面这点，实际上就可以运用排序，先给每个地堡对应的每个人的士兵数进行排序，然后问题就转化成了对\(n\)个地堡的分组背包问题，每个地堡选择一个人击败，获得击败所有小于等于这个人士兵数的奖励。

代码实现问题

因为不怎么写分组背包，代码实现还是出了问题。

一开始是这样写的，但是死活跑不过样例。

for (int k = 1; k <= n; k++)
{
	for (int i = 1; i <= s; i++)
	{
		for (int j = m; j >= w[k][i]; j--)
		{
			F[j] = max(F[j], F[j - w[k][i] * 2 - 1] + k * i);
		}
	}
}

实际上这个嵌套无法进行分组背包的过程。

带入内层循环很容易复发现，因为背包容量\(J\)是在每组的人员\(i\)内层枚举，导致这本质上还是零一背包，无法保证每组只选择一个。

改进方式很简单，把背包容量\(J\)是在地堡数量\(k\)下一层枚举即可。

for (int k = 1; k <= n; k++)
{
	for (int j = m; j >= 0; j--)
	{
		for (int i = 1; i <= s; i++)
		{
			if (j > w[k][i] * 2)
				F[j] = max(F[j], F[j - w[k][i] * 2 - 1] + k * i);
		}
	}	
}