HOJ 2182 Frog（简单DP）

简单DP
本题要点：
1、 注意，题目给出的昆虫的n个下标， 从 0 开始的。
2、dp[i][j] 跳i步，落在坐标j上，最多吃多少昆虫。
3、计算过程：
假如前面 的 i - 1 步 的所有位置已经计算完了。 现在走了 i步， 坐标是 j。
上一个状态可能是 走了 i - 1 步， 左边是 j - x （A <= x <= B）. 也就是 转态 dp[i][j]
可能是 转态 dp[i - 1][j - x] 转移而来的。 从 所有的 转态 dp[i - 1][j - x] （A <= x <= B）
选出最大的 max_s， dp[i][j] = max_s + insect[j]

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 110;
int T, n, A, B, k;
int insect[MaxN];	//insect[k] k点的昆虫数量
int dp[MaxN][MaxN];	//dp[i][j] 跳i步，落在坐标j上，吃的昆虫数void solve()
{
    for(int i = 0; i <= k; ++i)for(int j = 0; j <= n && j <= B * i; ++j)dp[i][j] = 0;dp[0][0] = insect[0];int ans = dp[0][0];for(int i = 1; i <= k; ++i){
    for(int j = A * i; j < n && j <= B * i; ++j)	// 当前坐标在 j点{
    int max_s = 0;for(int x = A; x <= B; ++x)	//从上一个位置 跳 x 步 来到的{
    if(j - x >= 0)max_s = max(max_s, dp[i - 1][j - x] + insect[j]);}dp[i][j] = max_s;ans = max(ans, dp[i][j]);
// printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);}}printf("%d\n", ans);
}int main()
{
    scanf("%d", &T);while(T--){
    scanf("%d%d%d%d", &n, &A, &B, &k);for(int i = 0; i < n; ++i)scanf("%d", &insect[i]);solve();}return 0;
}/* 1 4 1 2 2 1 2 3 4 *//* 8 */