poj 3661 Running (区间dp)
题意：锻炼，一共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]转移一下。
参考博客：参考博客
参考题解：
分析：先设dp[i][j]表示小明在i分钟，疲劳值为j时所能走的最远距离。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
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E4+7;
7const int M=505;
8int n;
9int m;
10int d[N];
11int dp[N][M];
12int main()
13{
14 #ifndef ONLINE_JUDGE
15 freopen("code/in.txt","r",stdin);
16 #endif
1// ios::sync_with_stdio(false);
2 cin>>n>>m;
3 for ( int i = 1 ; i <= n ; i++) scanf("%d",&d[i]);
ms(dp,0);
1 for ( int i = 1 ; i <= n ; i++)
2 {
3 dp[i][0] = dp[i-1][0];
4 for ( int j = 1 ; j <= m ; j++)
5 {
6 dp[i][j] = max(dp[i][j], dp[i-1][j-1]+d[i]);
7 if (i-j>=0)
8 dp[i][0] = max(dp[i-j][j],dp[i][0]);
9 // for ( int k = 1 ; k <= j-1 ; k++)
10 // dp[i-1+k][j-1-k] = max(dp[i-1][j-1],dp[i-1+k][j-1-k]);
11 }
1 }
2 int ans = dp[n][0] ;
3// for ( int i = 1 ; i <= n ; i++) ans = max(ans,dp[i][0]);
4// for ( int i = 1 ; i <= n ; i++)
5// for ( int j = 0 ; j <= m ; j++)
6// cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
7// cout<<dp[n][0]<<endl;
8 printf("%d\n",ans);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}