BZOJ 1613: [Usaco2007 Jan]Running贝茜的晨练计划 (dp)
1613: [Usaco2007 Jan]Running贝茜的晨练计划
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1468 Solved: 706 [Submit][Status][Discuss]
Description
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。 贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲劳度会增加 1。不过，无论何时贝茜的疲劳度都不能超过M(1 <= M <= 500)。如果贝茜选择休息，那么她的疲劳度就会每分钟减少1，但她必须休息到疲劳度恢复到0为止。在疲劳度为0时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0。 还有，在N分钟的锻炼结束时，贝茜的疲劳度也必须恢复到0，否则她将没有足够的精力来对付这一整天中剩下的事情。 请你计算一下，贝茜最多能跑多少米。
Input
第1行: 2个用空格隔开的整数：N 和 M
第2..N+1行: 第i+1为1个整数：D_i
Output
- 第1行: 输出1个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大 距离
Sample Input
5 2 5 3 4 2 10
Sample Output
9
输出说明:
贝茜在第1分钟内选择跑步（跑了5米），在第2分钟内休息，在第3分钟内跑 步（跑了4米），剩余的时间都用来休息。因为在晨跑结束时贝茜的疲劳度必须 为0，所以她不能在第5分钟内选择跑步。
题意：一个人第i分钟可以选择跑步或者休息，如果跑步可以跑d[i]米，疲劳度+1，如果休息疲劳度-1，但是一旦开始休息必须休息到疲劳度为0，疲劳度为0以后再休息疲劳度仍然为0，初始疲劳度为0，问n分钟最多跑多远。
思路：看出了是dp,想到了dp[i][j]的含义是i分钟疲劳度为j时能跑的最远距离。。但是看漏了“一旦开始休息必须休息到疲劳度为0”这个条件。。。
然后再之前的基础上改。。没改出来。。SAD…
的确是道很简单的dp..
转移方程为：
dp[i][0]=dp[i-1][0] //第i分钟一定可以不走。。。
dp[i][j] = max(dp[i][0],dp[i-j][j])(i>=j) //表示从i-j分钟休息，一直休息到第i分钟，使疲劳从j减小到0.
dp[i][j] = max(dp[i][j],dp[i-1][j-1]+d[i]) //表示第i分钟跑步。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月02日 星期六 16时08分47秒
4File Name :code/bzoj/1613.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E4+7;
34int n;
35int M;
36int d[N];
37int mx; //mx[i]表示到i分钟开始的时候疲劳度最多为多少
38int dp[N][505];
39void print()
40{
41 for ( int i = 0 ; i <= n ; i++)
42 {
43 int mx = n-i;
44 mx = min(i,mx);
45 for ( int j = 0 ; j <= mx ; j++)
46 {
47 cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
48 }
49 cout<<endl;
50 }
51}
52int main()
53{
54 #ifndef ONLINE_JUDGE
55 freopen("code/in.txt","r",stdin);
56 #endif
57
58 ios::sync_with_stdio(false);
59 cin>>n>>M;
60 for ( int i = 1 ; i <= n ; i++) cin>>d[i];
61 ms(dp,0);
62 for ( int i = 1 ; i <= n ; i++)
63 {
64 dp[i][0] = dp[i-1][0];
65 for ( int j = 1 ; j <= M ; j++)
66 {
67 if (i>=j)
68 dp[i][0] = max(dp[i][0],dp[i-j][j]); //从第i-j天连续休息j天到第i天疲劳度为0
69 dp[i][j] = max(dp[i][j],dp[i-1][j-1]+d[i]);
70 }
71 }
72// print();
73 cout<<dp[n][0]<<endl;
74
75 #ifndef ONLINE_JUDGE
76 fclose(stdin);
77 #endif
78 return 0;
79}