[普及/提高-]A105547.道具商店

题意

原题题意描述就足够清楚，这里不再重述。

思路

第一眼就能看出这是一个经典的 01 背包，但是观察数据范围就可以发现：如果使用正常以体积作为 dp 的一维的话绝对会 MLE，我们需要找到别的出路。

再次观察数据，注意到 $n \le 500 , a_i \le 500$，攻击力点数一定是小于等于 $250000$ 的。看到这我们考虑，既然不能把体积当作 dp 维度，那么反过来，把攻击力当作维度不就好了。

设 $dp_i$ 为当攻击力为 $i$ 时，所需要的最小金币数量。

初始状态：

$$dp_0 = 0,dp_i = INF \in \{1 , 250000\}$$

转移方程：
设 $i$ 为正在转移的物体，$j$ 为现在正在转移的增加的攻击力。

$$dp_j = \min(dp_j , dp_{j - a_i} + c_i)$$

最后从大到小遍历，直到 $dp_i \le k$ 后输出 $i$ 即可。

AC code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 250005;
int dp[N] , n , k , a[505] , c[505];
signed main(){
	cin >> n >> k;
	memset(dp , 0x3f , sizeof(dp));
	dp[0] = 0;
	for(int i = 1;i <= n;i ++){
		cin >> a[i] >> c[i];
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 250000;j >= a[i];j --){
			dp[j] = min(dp[j] , dp[j - a[i]] + c[i]);
		}
	}
	for(int i = 250000;i >= 0;i --){
		if(dp[i] <= k){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}