巫师与恶龙(wizard)

有后效性的dp问题

可以发现确定了要施的法术之后，施法的顺序一定按w值递增排序，因此对于读入的数据先排序
然后努力地想如何把v和w合并成一个权值，因为w值与后面节点的数量有关，可以顺势想到倒着做dp

$f[i][j]$表示从i到n中顺序选出j个法术能造成的最大伤害
$$f[i][j]=max(f[i+1][j],f[i+1][j-1]-w*(j-1)+v)$$

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int v, w;
} a[5005];
int n;
int f[5005][5005];

bool cmp(node x, node y)
{
    return x.w < y.w;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &a[i].v, &a[i].w);
    }
    sort(a + 1, a + n + 1, cmp);
    memset(f, 0xcf, sizeof f);
    f[n][1] = a[n].v;
    f[n][0] = 0;
    for (int i = n - 1; i >= 1; --i)
    {
        f[i][0] = 0;
        for (int j = 1; j <= n - i + 1; ++j)
        {
            f[i][j] = max(f[i + 1][j], f[i + 1][j - 1] + a[i].v - a[i].w * (j - 1));
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, f[1][i]);
    cout << ans << endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/yyhs%E6%A8%A1%E6%8B%9F2018/