好贷网好贷款

poj 3661 running

发布时间:2016-12-5 22:32:24 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 3661 running",主要涉及到poj 3661 running方面的内容,对于poj 3661 running感兴趣的同学可以参考一下。

题目叙述条件比较多:Bessie参加跑步比赛,每一分钟可以选择跑或者休息,同时给出每一分钟如果跑的话,可以跑的距离:跑的话,疲劳度会加1,对应的分钟可以跑对应的距离;休息的话,疲劳度减1;且疲劳度不可以超过m。跑完后疲劳度必须为0,求满足条件可以跑得最远距离。 我以为动态方程是这样的dp[i][j]=max(dp[i-1][j-1]+a,dp[i-1][j+1]); 但不是,可能是因为。当疲劳度为0时,再继续休息,仍是0。 所以思路整理如下: dp[i][j] 表示在第 i分钟,疲劳度为 j 的最优子状态,中间的状态转移比较麻烦。 首先,dp[i][j] = dp[ i - 1][ j - 1] + a[i] ,if j < m, and j <= i ( 每分钟最多可以加1) 其次,dp[i][0] = dp [i - 1][0] 表示第 i 分钟继续休息 也可以由以前的状态休息得来,eg: dp[4][0]<- dp[3][1],dp[2][2] dp[i][0] = min (dp[i][0], dp[ i - j][j] ), j <= m && i - j >= j ( dp[i-j][j]中,i-j不可能<j) 最后结果就是dp[n][0] 代码: #include <iostream> #include <cstring> using namespace std; int dp[10005][505]; int a[10005]; int max(int x,int y) {     return x>y?x:y; } int main() {     int i,j;     int n,m;     while(cin>>n>>m)     {         for(i=1;i<=n;i++)           cin>>a[i];     for(i=1;i<=n;i++)     {         for(j=1;j<=m&&j<=i;j++)         dp[i][j]=dp[i-1][j-1]+a[i];         dp[i][0]=dp[i-1][0];         for(j=1;j<=m&&i-j>=j;j++)         dp[i][0]=max(dp[i-j][j],dp[i][0]);     }     cout<<dp[n][0]<<endl;     }     return 0; }

上一篇:poj&nbsp;数论&nbsp;1845
下一篇:div css技巧,25个css样式技巧分享

相关文章

相关评论