定义状态d[i,j]表示进行到第i秒（还未对第i秒进行决策），疲倦程度为j之后，能够获得的最大距离。
第i秒有两种决策：继续跑、休息（注意到即使当前疲倦程度为0也是可以休息的），这样，
d[i,j]=max{ d[i+1,j+1]+r[i] (j+1<=m)
d[i+(j==0?1:j),0] (i+(j==0?1:j)<=n+1) }
以下是我的代码：
#include<iostream>
#include<string.h>
#define maxn 2002
#define maxm 501
#define inf 200000007
using namespace std;
long max(long a,long b){return (a>b?a:b);}
long n,m,r[maxn],d[maxn][maxm];
long dp(long i,long j)
{
if(d[i][j]!=-1) return d[i][j];
d[i][j]=-inf;
if(j+1<=m)
d[i][j]=max(d[i][j],dp(i+1,j+1)+r[i]);
if(i+(j==0?1:j)<=n+1)
d[i][j]=max(d[i][j],dp(i+(j==0?1:j),0));
return d[i][j];
}
int main()
{
cin>>n>>m;
for(long i=1;i<=n;i++)
cin>>r[i];
// Input
memset(d,-1,sizeof(d));
d[n+1][0]=0;
for(long i=1;i<=m;i++)
d[n+1][i]=-inf;
// Init
cout<<dp(1,0)<<endl;
// DP & Output
return 0;
}
posted on 2010-10-22 14:43
lee1r 阅读(627)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划