保卫泳池!
448 字
2 分钟
保卫泳池!
题目描述
你好,
我们听了说你正在开泳池派对。我们觉得那肯定很好玩。我们马上到。
谨启, 僵尸
收到信后你准备抵御一波僵尸进攻,手里拥有一定数量阳光 S,可以找疯狂戴夫购买 n 种植物。每种植物有固定阳光消耗 cost_i,并且拥有对应的防御分值 val_i,防御分值越高对抗僵尸能力越强。现在阳光总量有限,不能把所有植物全部买下。而且,因为疯狂戴夫忘记进货了,每种植物只剩一株。你想知道:在不超过总阳光的前提下,最大化总防御值。
输入描述
第一行两个整数 n, S。 1 <= n <= 100, 1 <= S <= 10^5 之后 n 行,每行两个整数 cost_i, val_i,(0 <= cost_i <= 1000) , (1 <= val_i <= 500)代表植物阳光消耗、防御值。
输出描述
第一行输出一个整数,能够得到的最大防御值。之后输出若干行,每一行输出买下植物的阳光消耗,防御值(先按阳光消耗从大到小排序,若阳光消耗量相同则按防御值从大到小排序)
示例1
输入
4 10050 6030 4020 2540 50输出
12550 6030 4020 25我的代码
#include <bits/stdc++.h>using namespace std;using ll=long long;int main (){ int n,s; cin>>n>>s; vector <int> cost(n+1,0); vector <int> def(n+1,0); vector <vector<int>> dp(n+1,vector <int>(s+1,0)); vector <vector<int>> ce(n+1,vector <int>(s+1,0)); vector <int> op; for(int i=1;i<=n;i++) { cin>>cost[i]>>def[i]; } for(int i=1;i<=n;i++) { for(int j=0;j<=s;j++) { if(j<cost[i]) { dp[i][j]=dp[i-1][j]; } else { dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost[i]]+def[i]); if(dp[i][j]>dp[i-1][j]) { ce[i][j]=1; } } } } cout<<dp[n][s]<<"\n"; int S=s;for(int i=n;i>=1;i--){ if(ce[i][S]==1&&S>=cost[i]) { op.push_back(i); S-=cost[i]; }} sort(op.begin(), op.end(), [&](int a, int b) { if (cost[a] != cost[b]) { return cost[a] > cost[b]; } return def[a] > def[b]; }); for (int id : op) { cout << cost[id] << " " << def[id] << "\n"; }
}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




