视频加载失败

保卫泳池!

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 100
50 60
30 40
20 25
40 50

输出

125
50 60
30 40
20 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";
}
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

保卫泳池!
https://www.xiaobaibai454.top/posts/study-26-10-27/
作者
Xiao_baibai
发布于
2026-10-27
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录