定義狀態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 閱讀(664)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃