제11회 산동성 대학생 프로그램 설계 경연대회 Adventurer's Guild(dp)

전송문
제목:
몬스터의 수량 n, 캐릭터의 생명력 H, 캐릭터의 공격 S 건네기;다음 n행, 매 행위 매 몬스터의 혈액량 h, 공격 s, 가치 w;
매번 몬스터를 처치할 때마다 h의 혈액량과 s의 공격을 소모한다. S가 마이너스일 경우 H로 S를 보충하고 H가 마이너스일 경우 끝난다.출력으로 얻을 수 있는 최대 가치;
아이디어:
가방 문제의 작은 변종, dp[i][j]가 소모한 혈액량은 i, 공격은 j가 얻을 수 있는 최대 가치;
Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define hz020 return
#define mes memset
#define mec memcpy

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int>pii;

const int N = 1010;
const int null = 0x3f3f3f3f;
const ll mod = 1000000007;

int n,H,S; 
ll dp[N][N];

int main()
{
     
	cin >> n >> H >> S;
	ll ans = 0;
	for(int i = 1;i <= n;i ++)
	{
     
		int h,s,w;
		cin >> h >> s >> w;
		for(int j = H;j > h;j --)
		{
     
			for(int k = S;k >= 0;k --)
			{
     
				if(j + k > h + s && j > h)
				{
     
					if(s > k)//    ，   
					{
     
						int x = h + s - k;
						dp[j][k] = max(dp[j][k],dp[j - x][0] + w);
						ans = max(ans, dp[j][k]);
					}
					else//   
					{
     
						dp[j][k] = max(dp[j][k],dp[j - h][k - s] + w);
						ans = max(dp[j][k],ans);
					}
				}
			}
		}
	}
	
	cout << ans << endl;
	
	hz020 0;
}