程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [dp] poj 3661 Running

[dp] poj 3661 Running

編輯:關於C++

題意:

一只奶牛可以跑n分鐘,疲勞度上限是m。

接下來是每分鐘可以跑a[i]米。

然後對於每分鐘可以選擇跑或者休息,跑的話疲勞度增加一點疲勞度。

休息的話每分鐘減少一點疲勞,但是如果選擇休息,那麼必須休息至疲勞度為零。

問n分鐘後,疲勞度為0的,所能跑的最遠距離。

思路:

水dp,dp[i][j]代表前i分鐘疲勞度為j跑的最遠距離。

狀態轉移就是跑或者休息。

代碼:

 

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#include"map"
using namespace std;
int dp[10245][512];
int v[10245];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(int i=1;i<=n;i++) scanf("%d",&v[i]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                if(j!=0 && i+j-1<=n ) dp[i+j-1][0]=max(dp[i+j-1][0],dp[i-1][j]);
                else  dp[i][0]=max(dp[i-1][0],dp[i][0]);
                if(j!=m) dp[i][j+1]=max(dp[i][j+1],dp[i-1][j]+v[i]);
            }
        }
        printf("%d\n",dp[n][0]);
    }
    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved