心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
定义状态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]!=-1return 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)  编辑 收藏 引用 所属分类: 题目分类:动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理