Problem A: 英雄无敌3（1）【dp/待补】

 

Problem A: 英雄无敌3（1）

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 86  Solved: 16
[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 

 

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct day {
    int s;
    int x;
    int y;
}a[50005];
int dp[50005], n;
int make_dp(int l,int r) {
    int Max = 0;
    for (int k = l; k <= n && k <= r; ++k) {
        if (dp[k] == 0) {
            if (a[k].x + k <= n)
                dp[k] = max(dp[k], a[k].s + make_dp(a[k].x + k, a[k].y + k - 1));
            else
                dp[k] = a[k].s;
        }
        Max = max(dp[k], Max);
    }
    return Max;
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d%d", &a[i].s, &a[i].x, &a[i].y);
            if (a[i].x == 0)
                a[i].x++;
            dp[i] = 0;
        }
        printf("%d
", make_dp(1,1));
    }
    return 0;
}