武器分配

Posted on Edited on In

题目大意：有 n 个堡垒排成一排构成了一条防御线。现在需要将 n 个武器放入这 n 个堡垒中，每个 堡垒放一个，每个武器有攻击力和战场贡献值两个属性。 由于这 n 个武器都不是人为操控的，所以会对其某半径内所有单位进行攻击，而这就导 致某些堡垒的互相攻击。现在发现第 i 个堡垒会和第 j 个堡垒互相攻击当且仅当|i-j|<=r， 且攻击力较低的武器和他所在的堡垒会破损。 现在你需要给出一种武器分配方案使得未破损武器的战场贡献值总和最大。为了方便你 只需输出战场贡献值总和的最大值即可。 多组数据(T≤10)，n是5000 首先不难发现，我们可以给他们按照攻击力的大小排序，会更方便我们后边的状态转移

且，我们还发现，对于一个被钦定的武器，如果发现ta在被钦定的武器里面是第i小的，在所有武器里面是第j小的，那么显然有\(i\times (r+1)\leq j​\)（最后一个武器除外，因为它最大最透彻所以他一定会被钦定）

然后就可以dp

状态：设\(f[i][j]\)表示决策了前j个武器，其中钦定了i个武器，且第j个武器必须被钦定，此时的最大价值

边界：\(i\times (r+1)\leq j||j==n\)

转移：

对于不合法的直接\(-\infty\)。

合法的：\(f[i][j]=max(f[i-1][k])+val[j](k<j)\)

这里的最大值可以用前缀最大值来优化，每次都更新一个或者说是统计一个\(sum[i][j]=max(sum[i][j-1],f[i][j])\)

其含义类比f数组

核心代码：来自ghj1222dalao

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
memset(a, 0, sizeof(a));

scanf("%d%d", &n, &r);
for (int i = 1; i <= n; ++ i)
    scanf("%d", &a[i].attack);
for (int i = 1; i <= n; ++ i)
    scanf("%d", &a[i].contribution);
sort(a + 1, a + 1 + n, cmp);
memset(f, 0xc0, sizeof(f));
memset(sum, 0, sizeof(sum));
f[0][0] = 0;

for (int i = 1; i <= n; i++) //选定了多少武器
{ 
    for (int j = 1; j <= n; j++) //所有武器
    {
        if (j >= i * (r + 1) || j == n)
        {
            f[i][j] = sum[i - 1][j - 1] + a[j].contribution;
            sum[i][j] = max(sum[i][j - 1], f[i][j]);
            ans = max(ans, f[i][j]);
        }
    }
} 
printf("%d\n", ans);