CSP临近，蒟蒻准备开始训练DP了 q w q qwq qwq
题意分析：
这是一道类似于
01
01
01背包的线性DP,它和一般的背包题唯一的不同点是，当不选择嗑药时，也要算上这种决策的“重量”。所以很容易想出这个
D
P
DP
DP的思路：
如果我们用
F
[
i
]
[
j
]
;
i
∈
[
0
,
n
]
,
j
∈
[
0
,
x
]
.
F[i][j];i\in[0,n],j\in[0,x].
F[i][j];i∈[0,n],j∈[0,x].
来表示对前
i
i
i个人用
j
j
j瓶药所能获得的经验值的最大值，那么有状态转移方程
F
[
i
]
[
j
]
=
{
m
a
x
(
F
[
i
−
1
]
[
j
]
+
l
[
i
]
,
F
[
i
−
1
]
[
j
−
u
[
i
]
]
+
w
[
i
]
)
;
j
≥
u
[
i
]
F
[
i
−
1
]
[
j
]
+
l
[
i
]
;
j
<
u
[
i
]
F[i][j]= \begin{cases} max(F[i-1][j]+l[i],F[i-1][j-u[i]]+w[i]);j\geq u[i]\\ F[i-1][j]+l[i];j<u[i] \end{cases}
F[i][j]={max(F[i−1][j]+l[i],F[i−1][j−u[i]]+w[i]);j≥u[i]F[i−1][j]+l[i];j<u[i]
两层循环即可，时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n, x;
int win[1005], lose[1005], use[1005];
long long f[1005][1005];
int main()
{
cin>>n>>x;
for (int i = 1; i <= n;i++)
{
cin >> lose[i] >> win[i] >> use[i];
}
for (int i = 1; i <= n;i++)
{
for (int j = x; j >= use[i];j--)
{
f[i][j] = max(f[i - 1][j] + lose[i], f[i - 1][j - use[i]] + win[i]);
}
for (int j = use[i] - 1; j >= 0;j--)
{
f[i][j] = f[i - 1][j] + lose[i];
}
}
cout << f[n][x]*5 << endl;
}