2021 山东省赛 H . Adventurer’s Guild(01背包)

描述：

Yuna traveled into the fantasy world. The gods of this world gave her a powerful set of equipment so that she could defeat many fifierce 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 hi health points and si stamina, and then she would get wi 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 afffford 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 (1≤n≤1000, 1≤H≤300, 0≤S≤300).

The next n lines describe all the monster crusade missions, where the i-th line contains three integers hi,si,wi (0≤hi,si≤300, 1≤wi≤109).

输出：

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

大意：

异世界的尤娜有 生命值和耐力值，打怪消耗生命值和耐力值，获得金币，当生命值小于 0 即死亡，耐力值小于 0时耐力值重置为 0，消耗生命值。

思路：

一个01背包问题，直接写了

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e5+100;
const int p = 1e4;
const double eps = 1e-8;
ll dp[301][301];// j h    k  s 
int n,h,s;
int hs[1001],ss[1001],wss[1001];
int main()
{
  cin>>n>>h>>s;
  for(int i=1;i<=n;i++)
  {
    cin>>hs[i]>>ss[i]>>wss[i];
  }//hs健康，ss耐力,wss金币
  for(int i=1;i<=n;i++)
  {
    for(int j=h;j>=0;j--)
    {
      for(int k=s;k>=0;k--)
      {
        if(j>hs[i]&&k>=ss[i])//当生命与耐力都足够时
          dp[j][k]=max(dp[j][k],dp[j-hs[i]][k-ss[i]]+wss[i]);
        else
        if(k<ss[i]&&j+k>(hs[i]+ss[i]))
          dp[j][k]=max(dp[j][k],dp[k+j-(hs[i]+ss[i])][0]+wss[i]);//当耐力不够但是生命＋耐力足够时，注意此时耐力清零
      }
    }
  }
  cout<<dp[h][s];
  return 0;
}

反思：

当耐力不够的时候，应该是生命值去抵消多出的耐力消耗值，而且此时耐力值清零，注意这两个易错点