Problem A: 英雄无敌3（1）
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 87 Solved: 17
[ Submit][ Status][ Web Board]
Description
大家知道在英雄无敌3中，每个城堡都需要钱来维持建设，现在有一座很奇怪的金矿，它在第i天只产生si 元的钱，而且如果你在第i天拿到si 元的钱，那么你将在 xi 内（包括第i天）拿不到钱，而在yi天内（包括第i天）一定要再次拿钱。现在有一个着急的玩家，他现在已经拿了第一天的钱，他想知道他最多能拿到多少钱（包含第一天的钱）。
Input
第一行输入一个数t,代表测试案例数
每个案例先输入一个数n（n < =50000），代表总共有几天，接下来有n行，输入3个整数整数分别为si，xi，yi (0<=si<10000,0<=xi < yi)
Output
对于每组案例，输出一个正整数，代表他能拿到的最多钱数
Sample Input
4
3
1
1 2
2 2 3
3 3 4
3
1 1 3
2 2 4
3 3 5
4
10 3 10
7 1 7
5 2 5
1 1 2
5
1 1 9
10 3 10
7 1 7
5 2 5
1 1 2
Sample Output
3
4
11
13
HINT
直接正向dp，以x y为区间，动态方程dp[j]=max(dp[j],dp[i]+s[i])，不过可能有特殊情况要判断。而且第一天必须取。。。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int s[60000],x[60000],y[60000],dp[60000];
int main(){
int t,n,i,j,ans;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(dp,0,sizeof(dp));ans=0;
for(i=0;i<n;i++)scanf("%d%d%d",&s[i],&x[i],&y[i]);
for(i=x[0];i<y[0]&&i<n;i++)dp[i]=dp[0]+s[0];
for(i=x[0];i<n;i++)if(dp[i]){
for(j=i+(!x[i]?1:x[i]);j<i+y[i]&&j<n;j++)dp[j]=max(dp[j],dp[i]+s[i]);
if((i+(!x[i]?1:x[i]))>=n)ans=max(ans,dp[i]+s[i]);
}
for(i=0;i<n;i++)ans=max(ans,dp[i]);
printf("%d\n",ans);
}
}