[Leaf] [P5322] 排兵布阵

luogu-p5322-排兵布阵">Luogu-P5322 排兵布阵

1. 题面梗概

中译中: 有 $N$ 个城堡，$M$ 个士兵，$S$ 个对手。第 $i$ 座城堡的驻兵为 $a_i$，若你派出的兵力 $\geq 2a_i + 1$，则获胜，获得 $i$ 得分。求最终获得的最大分数。

2. 逻辑推导

对手有很多，派兵的规则也有点复杂，看起来像一个动态的博弈问题。但关键在于，每个决策都是独立的。

这意味着什么？这意味这我们可以把每个城堡的派兵看作是一个独立的“背包”，通过广义背包的定义，我们发现这个问题可以通过分组背包来解决。

2.1 策略

对于第 $i$ 个城堡，想要获胜的代价很明显就是 $2a[i] + 1$，而每个城堡会有多个对手派兵，如果我们想战胜 $k$ 个人，我们的最小代价显然是 $2a[i][k] + 1$ 。

那么在第 $i$ 个城堡中，我们就有 $S + 1$ 种决策，赢 $0, 1, \dots, s$ 人。注意：同一个城堡的斗争中，只能选择一种决策方案。

2.2 背包

那么就是很裸的分组背包了。每一个城堡是一个物品组，每一组里有 $S + 1$ 个互斥的决策。

那我们只需要预处理跑出每一组赢 $k$ 个人的代价和收益，跑一遍 DP 即可。

3. 代码实现

▶

AcCode

// 分组背包
#include<bits/stdc++.h>
using namespace std;

const int maxn = 100 + 5;
const int maxm = 2e4 + 50;

int s, n, m;
int a[maxn][maxn];
int dp[maxm];

int main()
{	
    cin >> s >> n >> m;
    for( int j = 1; j <= s; ++ j )
    {
        for( int i = 1; i <= n; ++ i )
        {
            cin >> a[i][j];
        }
    }

    for( int i = 1; i <= n; ++ i )
    {
        sort( a[i] + 1, a[i] + s + 1 );
        for( int j = 1; j <= s; ++ j )
        {
            a[i][j] = a[i][j] * 2 + 1;
        }
    }

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

    cout << dp[m] << '\n';
    return 0;
}

4. 复盘

• 复杂度: $O( N \cdot M \cdot S )$。

• 碎碎念: 分组背包的关键，或者说背包问题的关键，往往在于建模，通过广义背包的定义，我们可以把赢几个人变成了互斥的物品，从而使用分组背包来处理这个博弈问题。

• 关联笔记: 背包DP