hdu 6495 冰水挑战

 表示在考虑完前  个挑战后，并且接受了  个挑战的剩余体⼒的最⼤值

首先确定我们的是越大越有利于后面。

所以我们每一次转移就是接受第  个挑战和不接受第  个挑战，

不接受的话(此时 i != j)，

接受的话，

取最大，算一下就是答案

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
	ll a;
	ll b;
	ll c;
}que[1005];
ll dp[1005][1005];
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		memset(dp, 0, sizeof(dp));
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)
			scanf("%lld%lld%lld", &que[i].a, &que[i].b, &que[i].c);
		dp[0][0] = m;
		for (int i = 1; i <= n; i++)
			dp[i][0] = dp[i - 1][0] + que[i].c;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= i; j++)
			{
				if (i > j)
					dp[i][j] = dp[i - 1][j];
				ll temp = min(dp[i - 1][j - 1], que[i].b) - que[i].a;
				dp[i][j] = max(dp[i][j], temp);
				if (dp[i][j] > 0)
					dp[i][j] += que[i].c;
			}
		}
		int cnt = 0;
		for (int i = n; i >= 0; i--)
		{
			if (dp[n][i] > 0)
			{
				cnt = i;
				break;
			}
		}
		printf("%d\n", cnt);
	}
}