链接: https://vjudge.net/problem/HDU-2182
题意:
有一只青蛙, 有 n 个节点, 开始时在 1 节点, 有 k 次往右跳的机会, 每次跳的距离是 a-b 之间.
每个节点有一个值, 到达那个节点则总值加上那个值.
求最大能得到的值
思路:
dp[i][j] 表示第 i 个节点, 第 j 次跳跃得到的值.
dp[1][0] = a[0]. 因为第一个节点不用跳就能得到.
代码:
- #include <iostream>
- #include <memory.h>
- #include <vector>
- #include <map>
- #include <algorithm>
- #include <cstdio>
- #include <math.h>
- #include <queue>
- #include <string>
- #include <stack>
- #include <iterator>
- using namespace std;
- typedef long long LL;
- const int MAXN = 1000 + 10;
- int dp[MAXN][MAXN];
- int a[MAXN];
- int main()
- {
- int t;
- int n, l, r, k;
- scanf("%d", &t);
- while (t--)
- {
- memset(dp, 0, sizeof(dp));
- scanf("%d%d%d%d", &n, &l, &r, &k);
- for (int i = 1;i <= n;i++)
- scanf("%d", &a[i]);
- dp[1][0] = a[1];
- for (int i = 1;i <= n;i++)
- {
- for (int j = i - r;j <= i - l;j++)
- {
- if (j < 1)
- continue;
- for (int m = 1;m <= k;m++)
- dp[i][m] = max(dp[i][m], dp[j][m - 1] + a[i]);
- }
- }
- int res = 0;
- for (int i = 1;i <= n;i++)
- for (int j = 1;j <= k;j++)
- res = max(res, dp[i][j]);
- printf("%d\n", res);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3008127.html