Problem Description
Polar Bear Pitching helps you crystallize your message.
The stage could not be any cooler, and we mean literally:
a hole cut through the ice in the frozen Baltic Sea.
2050有一项很有挑战的活动 —— Polar Bear Pitching 。
体验人跳入冰水中讲述自己的恐惧,改变以及梦想。这是没有时间限制的演讲,就看你能在冰水中呆多久!
现在,我们要依次面对 n 个冰水挑战,每个挑战你都可以选择接受或不接受。接受第 i 个挑战会让你丧失 ai点体力,因为每个挑战所处的环境不同,如果你要挑战它,在挑战它之前你的体力 x 会变成 min(x,bi),当你完成这个挑战的时候,你的体力会变成 x−ai,体力任何时候不允许小于等于 0,无论你是否接受第 i 个挑战,在这个挑战结束以后你的体力都会增加 ci。
现在我们想知道最多可以完成多少个挑战。
Input
第一行一个正整数 T (T≤50) 表示数据组数。
接下来 T 组数据,每组第一行两个正整数 n,c (1≤n≤103,1≤c≤109),表示挑战的数量和初始体力,接下来 n 行,每行三个非负整数 ai,bi,ci(0≤ai,bi,ci≤109)。
Output
对于每组数据输出一行一个数,表示你最多能完成几个挑战。
Sample Input
2
3 10
1 2 0
4 8 3
6 10 1
2 1
1 1 1
1 1 1
Sample Output
2
0
解题思路:dp[i][j]=k表示前i个挑战了j个剩下的最大体力
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=1e3+5; const int inf=0x3f3f3f3f; ll a[N],b[N],c[N]; ll dp[N][N]; //前i个挑战了j个时候的最大体力值 int main() { int n,m,k,_; ll C; scanf("%d",&_); while(_--) { memset(dp,0,sizeof(dp)); scanf("%d%lld",&n,&C); memset(dp,-1,sizeof(dp)); dp[0][0]=C; for(int i=1;i<=n;i++) scanf("%lld%lld%lld",a+i,b+i,c+i); for(int i=1;i<=n;i++) { for(int j=0;j<=i;j++) { if(dp[i-1][j]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j]+c[i]); //不挑战第i个 if(j==0) dp[i][j]=dp[i-1][j]+c[i]; //挑战第i个 else if(dp[i-1][j-1]!=-1&&(dp[i-1][j-1]>0&&b[i]>0)&&min(dp[i-1][j-1],b[i])-a[i]>0) { dp[i][j]=max(dp[i][j],min(dp[i-1][j-1],b[i])-a[i]+c[i]); } } } for(int i=n;i>=0;i--) { if(dp[n][i]>0) { printf("%d ",i); break; } } } }