HDU2182 Frog

首先，原谅我写这么简单的dp题解，其是是因为我dp基础非常差

题意

给定4个数N,A,B,K,在[0,N)上每个坐标上都有一些昆虫，现在一只在坐标0的青蛙可以原地不动或通过向右跳A至B步，总共可以跳K次，问最多能够吃到多少只昆虫？

分析

首先考虑阶段性，跳i步的方案，不会影响跳i+1步的方案，所以阶段性就是先计算跳前i步，然后再计算跳前i+1步。
状态表示dp[i][j]:跳跃前i步之后，落在位置j的方案数
状态转移：dp[i][j] = max(dp[i][j],dp[i-1][j-k]) k是跳跃的步长
然后看到状态转移dp[i][j]只会与上一轮有联系，所以可以使用动态数组,虽然也在本题也节省不了多少内存

AC代码
使用了动态数组

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6+100;
typedef long long ll;

int T;
int N,A,B,K;
int arr[111],dp[111];
int main(){
    cin>>T;
    while(T--){
        memset(dp,0,sizeof dp);
        scanf("%d%d%d%d",&N,&A,&B,&K);
        for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);

        int res = 0;
        dp[1] = 1;
        for(int i = 1;i<=K;i++){
            for(int j = N;j>=1;j--){
                for(int k = A;k<=B;k++){
                    if(j-k>=1) dp[j] = max(dp[j],dp[j-k]+arr[j]);
                }
                res = max(res,dp[j]);
            }
        }
        printf("%d\n",res);
    }
    return 0;
}