30 lines
778 B
C++
30 lines
778 B
C++
// lanqiao 2223 背包与魔法
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
#define int long long
|
|
const int N = 1e4 + 10;
|
|
int dp[N][2];
|
|
signed main()
|
|
{
|
|
// 请在此输入您的代码
|
|
int n, m, k; cin >> n >> m >> k;
|
|
for(int i = 1; i <= n; i++){
|
|
int w, v; cin >> w >> v;
|
|
for(int j = m; j >= 0; j--){
|
|
if(j >= w){
|
|
dp[j][0] = max(dp[j][0], dp[j-w][0] + v); // 未使用魔法
|
|
dp[j][1] = max(dp[j][1], dp[j-w][1] + v); // 可以使用魔法, 但不是本次
|
|
}
|
|
// 使用魔法, 但必须从未使用魔法状态转移, 否则会导致多次使用魔法
|
|
if(j >= (w+k)) dp[j][1] = max(dp[j][1], dp[j-w-k][0] + 2*v);
|
|
}
|
|
}
|
|
cout << max(dp[m][1], dp[m][0]) << '\n';
|
|
return 0;
|
|
}
|
|
/* test samples -> 26
|
|
3 10 3
|
|
5 10
|
|
4 9
|
|
3 8
|
|
*/ |