Luogu-P5322

题面

题目大意

小C正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡,每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵,可以向第$i$座城堡派遣 $a_i$ 名士兵去争夺这个城堡,使得总士兵数不超过 $m$。
如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍,那么这名玩家就占领了这座城堡,获得 $i$ 分。

现在小C即将和其他 $s$ 名玩家两两对战,这 $s$ 场对决的派遣士兵方案必须相同。小C通过某些途径得知了其他 $s$ 名玩家即将使用的策略,他想知道他应该使用什么策略来最大化自己的总分。
其中

且有

你需要输出小C总分的最大值

这题乍一看没什么头绪,我们不妨把在每座城堡派出的兵力看做是体积,占领每座城堡所得的积分看作是价值。那么很显然这是一道背包问题的题目。
每座城堡都是一个泛化的物品。

那么如果在第i座城堡派出的兵力是 $x_i$ 则我们的得分函数$p$是

很容易推出状态转移方程($M$为总兵力)

代码

1
#include <iostream>
2
#include <algorithm>
3
4
using namespace std;
5
const int maxs = 105;
6
const int maxn = 105;
7
const int maxm = 20005;
8
9
int a[maxn][maxn];
10
int F[maxm];
11
12
inline auto pkg(int k, int i, int S) -> int {
13
    int p = 0;
14
    for (int t = 1; t <= S; ++t) {
15
        p += int(k > 2 * a[t][i]) * i;
16
    }
17
    return p;
18
}
19
20
auto main() -> int {
21
    ios::sync_with_stdio(false);
22
    cin.tie(nullptr);
23
    cout.tie(nullptr);
24
    //S城堡数 N玩家数 M棋子数
25
    int S, N, M;
26
    cin >> S >> N >> M;
27
    for (int i = 1; i <= S; ++i) {
28
        for (int j = 1; j <= N; ++j) {
29
            cin >> a[i][j];
30
        }
31
    }
32
    for (int i = 1; i <= N; ++i) {
33
        for (int v = M; v >= 0; --v) {
34
            for (int k = 0; k <= v; ++k) {
35
                int p = pkg(k, i, S);
36
                F[v] = max(F[v], F[v - k] + p);
37
            }
38
        }
39
    }
40
    cout << F[M] << endl;
41
    return 0;
42
}

很显然这么做的复杂度为

然后就很愉快的TLE六个点(大哭)

那么该怎么做呢?我们可以这样想,我们将每个人在$i$城堡派的兵力排序,如果$x_i > 2a_{i,t_0}$且$x_i \leq 2a_{i,t_0 + 1}$那么对于所有$t\leq t_0$都有$x_i > 2a_{i,t}$
则此时在$i$城堡得分为 $t_0i$
此时的状态转移方程为

时间复杂度为

很显然可以AC啦

1
#include <iostream>
2
#include <algorithm>
3
4
using namespace std;
5
const int maxs = 105;
6
const int maxn = 105;
7
const int maxm = 20005;
8
9
int a[maxn][maxn];
10
int F[maxm];
11
12
auto main() -> int {
13
    ios::sync_with_stdio(false);
14
    cin.tie(nullptr);
15
    cout.tie(nullptr);
16
    //S城堡数 N玩家数 M棋子数
17
    int S, N, M;
18
    cin >> S >> N >> M;
19
    for (int i = 1; i <= S; ++i) {
20
        for (int j = 1; j <= N; ++j) {
21
            cin >> a[j][i];
22
        }
23
    }
24
    for (int i = 1; i <= N; ++i) {
25
        sort(a[i] + 1, a[i] + S + 1);
26
    }
27
    for (int i = 1; i <= N; ++i) {
28
        for (int v = M; v >= 0; --v) {
29
            for (int k = 1; k <= S; ++k) {
30
                if(v >= 2 * a[i][k] + 1) {
31
                    F[v] = max(F[v], F[v - 2 * a[i][k] - 1] + i * k);
32
                }
33
            }
34
        }
35
    }
36
    cout << F[M] << endl;
37
    return 0;
38
}