HDU - 2182 Frog
有一只青蛙，有n个节点，开始时在1节点，有k次往右跳的机会，每次跳的距离是a-b之间
每个节点都有一定的值，求青蛙在K跳之后能够获得的最大的值
dp[ i ][ j ] 为青蛙跳j次到达i位置可以吃到的最多的昆虫数。
状态转移方程为
dp[ i ][ j ] = max( dp[ i ][ j ] , dp[ t ][ j - 1 ] + cnt[ i ] )，
需要注意青蛙起点的昆虫数量。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int cnt[110],dp[110][110];
int n,a,b,k;
int main()
{
int t;scanf("%d",&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",&cnt[i]);for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)for(int r=i+a;r<=i+b&&r<=n;r++)dp[r][j]=max(dp[r][j],dp[i][j-1]+cnt[r]);printf("%d\n",dp[n][k]+cnt[1]);}return 0;
}