列表

详情

NC221737. Adventurer'sGuild

描述

Yuna traveled into the fantasy world. The gods of this world gave her a powerful set of equipment so that she could defeat many fierce monsters. However, she had limited health points and stamina, and she could not kill a large number of monsters.

Adventurer's guild would release n monster crusade missions, such as black python and wild wolf. Completing the i-th mission would consume Yuna h_i health points and s_i stamina, and then she would get w_i gold coins.

In the beginning, Yuna had H health points and S stamina. When her health points were dropped to less than or equal to 0, she would die. However, when her stamina was dropped to less than 0, she would not give up, and then the overdrawn stamina would be reduced from health points. For example, her health points would be reduced by 3, when her stamina dropped to -3, and then her stamina would be reset to 0. If her health points can not afford the overdrawn stamina, she would also die.

As a friend of Yuna, can you help her choose some missions to complete to get the maximum number of gold coins? Make sure Yuna does not die, or you will be very sad.

输入描述

The first line contains three integers n,H,S .

The next n lines describe all the monster crusade missions, where the i-th line contains three integers h_i, s_i, w_i .

输出描述

Print one integer -- the maximum number of gold coins that Yuna could get.

示例1

输入: 

2 66 22
1 23 2
66 8 90

输出: 

2

示例2

输入: 

4 16 22
1 23 11
5 8 14
2 36 99
15 22 27

输出: 

27

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 123ms, 内存消耗: 1828K, 提交时间: 2021-05-26 19:32:48 

#include <bits/stdc++.h>
using namespace std;
#define int long long
int f[310][610];
int n,H,S,h,s,w;

signed main()
{
	cin>>n>>H>>S;
	for (int i=1;i<=n;++i)
	{
		cin>>h>>s>>w;
		for (int j=H;j>=h;--j)
			for (int k=S+H;k>=h+s;--k)
				f[j][k]=max(f[j][k],f[j-h][k-h-s]+w);
	}
	cout<<f[H-1][H+S-1]<<endl;
	return 0;
}

上一题

© 2024 nowcoder.com