有后效性的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)$$
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #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;
}
|
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/yyhs%E6%A8%A1%E6%8B%9F2018/
