WA#4求调
查看原帖
WA#4求调
1235819
_std_xzh楼主2024/8/5 20:25
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
// const double x = 5.0 / 4;
int n , t , k , v[105] , h[105] , dp[1000005] , maxn;
bool f;
int main() {
	cin >> n >> t >> k;
	for(int i = 1;i <= n;i++){
		cin >> v[i] >> h[i];
	}
	for(int i = 1;i <= n;i++){
		if(h[i] >= k){
			f = 1;
			memset(dp , 0 , sizeof(dp));
			for(int j = 1;j <= n;j++){
				// if(j == i)continue;
				for(int k = h[j];k <= t * 5 / 4;k++)dp[k] = max(dp[k] , dp[k - h[j]] + v[j]);
			}
			// cout << dp[n] << " ";
			maxn = max(maxn , dp[(t - h[i]) * 5 / 4] + v[i]);
		}
	}
	if(!f){
		for(int i = 1;i <= n;i++){
			for(int j = i;j <= t;j++)dp[j] = max(dp[j] , dp[j - h[i]] + v[i]);
		}
		cout << dp[t];
	}
	else cout << maxn;
    return 0;
}
2024/8/5 20:25
加载中...