题解 P5322 【[BJOI2019]排兵布阵】

1010000_1001010 · 2019-11-10 10:18:59 · 题解

开始看到这道题的时候没什么头绪，后来仔细想想，发现对数据预处理之后就是一个经典的分组背包问题。

大概思路如下：

• 将一个城堡看作一组
• 先对每组城堡中的各个玩家的敌人数进行排序
• *每个玩家派兵的数量2+1** 可以看作为物品重量（注意玩家派兵数量可能相同）
• 那么 排序后该玩家敌人数的索引与城堡索引的乘积 就是物品价值 且每个组内的物品只能选择一次

于是我们就把这个问题转化为了分组背包问题

状态转移方程如下（i代表第几组，j代表该组第几个)

f[v]=max(f[v],f[v-weight[i][j]]+value[i][j])

剩下的就用套用模板就行了
样例代码 :

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

using namespace std;

int main()
{

    int s, n, m; //分别表示除了小C以外的玩家人数、城堡数和每名玩家拥有的士兵数（背包容量）。
    cin >> s >> n >> m;

    int value[n][s], weight[n][s]; //物品个数为n*s
    int f[m + 1];
    memset(f, 0, sizeof(f)); //赋初值
    memset(value, 0, sizeof(value));
    memset(weight, 0, sizeof(weight));

    int data[n][s];
    for (int i = 0; i < s; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> data[j][i];
        }
    }

    for (int i = 0; i < n; i++)
    {                               //第几座城
        sort(data[i], data[i] + s); //拍一个序
        for (int j = 0; j < s; j++)
        {
            if (j == s - 1 || data[i][j] != data[i][j + 1])
            { //防止出现重叠现象
                value[i][j] = (j + 1) * (i + 1);
                weight[i][j] = data[i][j] * 2 + 1;
            }
        }
    }
    //就是一个分组背包问题

    for (int i = 0; i < n; i++)
    {
        for (int v = m; v >= 0; v--)
        {
            for (int j = 0; j < s; j++)
            {
                if (v >= weight[i][j] && weight[i][j] != 0)
                {
                    f[v] = max(f[v], f[v - weight[i][j]] + value[i][j]);
                }
            }
        }
    }
    cout << f[m] << endl;
    system("pause");
    return 0;
}