题目链接：点击打开链接

题意： 在一条直线上运动，每分钟可以运动距离a[i] ,每分钟可以选择运动或者休息，有一个疲劳系数，最初为0，每运动一分钟疲劳系数加1,（不能大于m） 同理，每休息一分钟，疲劳系数减1，（不能小于0）求n分钟后最大运动距离，要求n分钟时疲劳系数要为0.

两个状态，当前时间及当前疲劳系数。设 dp[i][j] =dp[i-1][j-1]+a[i] (j>0) else  dp[i][j] =max(dp[i][j],max(dp[i-k][0],dp[i-k][k]) ) (k<=m&&k<i) 即 当前疲劳系数为0时，可能是从前面的状态休息过来的，取最大。 最后输出dp[n][0]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 1<<12
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
using namespace std;
int dp[10002][502],n,m,a[10002];
void solve()
{
	memset(dp,0,sizeof(dp));
	dp[1][0]=0;dp[1][1]=a[1];
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			if(j==0)
			{
				int tem=-1;
				for(int k=0;k<=m&&k<i;k++)
					tem=max(tem,max(dp[i-k][0],dp[i-k][k]));
				dp[i][0]=tem;
			}
			else
			dp[i][j]=dp[i-1][j-1]+a[i];
		}
	}
	printf("%d\n",dp[n][0]);
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;i++)
			scanf("%d",a+i);
		solve();
	}
    return 0;
}

POJ 3661-Running（DP）