poj 3661 Running (区间dp)

Posted by 111qqz on Monday, July 25, 2016

TOC

poj 3661题目链接

题意:锻炼,一共n分钟,每分钟可以选择跑步或者休息,第i分钟跑步可以跑d[i]米,并增加一点疲劳度,如果选择休息,那么每分钟减少1点疲劳值。一旦开始休息,必须休息到疲劳值为0才能再次开始跑步。疲劳值不能超过m.第n分钟的时候疲劳值必须为0,否则之后会感觉身体被掏空。问n分钟最远多多远。

思路:

我能想到的:

  * dp[i][j]表示第i分钟疲劳度为j的时候能跑的最远距离
  * 初始化dp为0.
  * 最后的答案为dp[n][0]
  * 如果第i分钟跑步,转移方程为dp[i][j] = max(dp[i][j],dp[i-1][j-1]+d[i]);

我想错了的:

  * 休息的时候的转移方程应该是第i天刚好**休息好**时:dp[i][0]=max(dp[i-j][j],dp[i][0]) 而不是**开始休息**时
  * 由于是第i天休息好时的状态,那么开始休息的时间是固定的(第i-j天),只进行一个转移,而不会影响中间的那些天

我想的不够好的:

  * 考虑到了可能最后几天为了疲劳度为0干脆就不跑,我的做法是取了所有的dp[i][0]的最大值。但是更好的做法似乎是dp[i][0] = dp[i-1][0]转移一下。

参考博客:参考博客

参考题解:

a)、先看dp[i][0]的情况,表示第i分钟时,疲劳值为0,考虑这个值由哪些情况得到,1、dp[i][0] = dp[i-1][0],这个没有任何问题。2、dp[i][0] = dp[i-j][j]。表示i-j分钟时的疲劳值为j,然后一直休息j分钟把疲劳值降成0。

b)、现在考虑dp[i][j]的情况,它可以由dp[i-1][j-1] + Di得到,表示第i分钟选择走Di。因为要保证没有后效性,所以只有这一种情况可以转移。

/* ***********************************************
Author :111qqz
Created Time :2016年07月25日 星期一 23时42分26秒
File Name :code/poj/3661.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=2E4+7;
const int M=505;
int n;
int m;
int d[N];
int dp[N][M];
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif

//	ios::sync_with_stdio(false);
    cin>>n>>m;
    for ( int i = 1 ; i <= n ; i++) scanf("%d",&d[i]);

    ms(dp,0);

    for ( int i = 1 ; i <= n ; i++)
    {
        dp[i][0] = dp[i-1][0];
        for ( int j = 1 ; j <= m ; j++)
        {
        dp[i][j] = max(dp[i][j], dp[i-1][j-1]+d[i]);
        if (i-j>=0)
            dp[i][0] = max(dp[i-j][j],dp[i][0]);
    //	for ( int k = 1 ; k <= j-1 ; k++)
    //	    dp[i-1+k][j-1-k] = max(dp[i-1][j-1],dp[i-1+k][j-1-k]);
        }

    }
    int ans = dp[n][0] ;
//	for ( int i = 1 ; i <= n ; i++) ans = max(ans,dp[i][0]);
//	for ( int i = 1 ; i <= n ; i++)
//	    for ( int j = 0 ; j <= m ; j++)
//		cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
//	cout<<dp[n][0]<<endl;
        printf("%d\n",ans);


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付