Problem A: 英雄无敌3（1）【dp/待补】
<center>
Submit: 86 Solved: 16
[ Submit][ Status][ Web Board] </center>
Problem A: 英雄无敌3（1）
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 86 Solved: 16
[ Submit][ Status][ Web Board] </center>
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\n", make_dp(1,1));
}
return 0;
}
投递美团等公司6个岗位