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
************************************************ */
#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;
}