题解：P11377 [GESP202412 七级] 武器购买

思路

这是一个典型的背包问题。

我们可以设 \(dp_{j}\) 为武器总强度为 \(j\) 的情况下的最小花费。

于是，根据背包问题的模型我们就能得出：

最终，答案就为第一个大于等于 \(P\) 的 \(dp_j\) 的下标 \(j\)。

时间复杂度为 \(O(TnQ)\)。

代码

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define rep( i , l , r ) for (int i = (l) ; i <= (r) ; i++)
#define per( i , r , l ) for (int i = (r) ; i >= (l) ; i--)
int n , P , Q ;
int p[110] , c[110] ;
int dp[50010] ;
void solve (){
	memset (dp , 0 , sizeof dp) ;
	cin >> n >> P >> Q ;
	rep (i , 1 , n){
		cin >> p[i] >> c[i] ;
	}
	rep (i , 1 , n){
		per (j , Q , c[i]){
			dp[j] = max (dp[j] , dp[j - c[i]] + p[i]) ;
		}
	}
	rep (j , 0 , Q){
		if (P <= dp[j]){
			cout << j << '\n' ;
			return ;
		}
	}
	cout << -1 << '\n' ; 
}

signed main (){
	int _ = 1 ;
	cin >> _ ;
	while ( _-- ){solve () ;}
	return 0 ;
}