[POJ - 3661] Running

发表于 | 更新于 | 分类于 ， ，
本文字数： 16k

链接

\(\text{POJ - 3661}\)

题意

  \(\text{Bessie}\)在一个直赛道上跑步，他需要跑\(\text{N}\)分钟，其中第\(i\)分钟他能跑\(d_i\)米，同时他还有一个最大疲劳值\(M\)，开始的时候它的疲劳值为\(0\)，跑步的时候每一分钟他都可以选择跑与不跑，如果跑的话，他的疲劳值就会增加\(1\)，如果选择休息，他的疲劳值就会下降，但是他只能等疲劳值下降到\(0\)才能再次跑，现在你需要求出\(\text N\)分钟之后，他的疲劳值为\(0\)时他能跑的最大距离是多少。

  数据范围：\(1\leq \text{M} \leq 500\)，\(1\le d_i\le 1000\).

分析

  这是一道区间\(dp\)的题目；

  \(dp[i][j]\)表示跑完\(i\)分钟，疲劳值为\(j\)时所能跑的最大距离；那么对于一个状态\(dp[i][j]\)，他有可能从两种状态转移过来，一种是第\(i\)分钟跑了，对于这种状态有\(dp[i][j]=dp[i-1][j-1]+a[i]\)，另一种情况是没跑，对于没跑的情况，有可能\(i-1\)分钟也没跑，第\(i\)分钟没跑也只是一个中间状态，这样就无法求解，所以我们需要考虑\(dp[i][0]\)，\(dp[i][0]\)一定是由\(dp[i-j][j]\)转移而来的（对于休息的情况，直接考虑开始休息和结束休息，中间不考虑）；

  即对于第\(i\)分钟休息和跑的情况分开考虑。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
	//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
	//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
	inline int read() {
		char c = getchar(); int x = 0, f = 1;
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
		return x * f;
	}
}

using namespace fastIO;
using namespace std;

namespace segment_Tree {
	struct Tree {
		int l, r, max;
	} tree[4 * MAXN];

	inline void push_up(int x) {
		tree[x].max = max(tree[x << 1].max, tree[x << 1 | 1].max);
	}

	inline void build(int x, int l, int r) {
		tree[x].l = l, tree[x].r = r;
		if (l == r) {
			tree[x].max = 0;
			return;
		}
		int mid = (l + r) >> 1;
		build(x << 1, l, mid);
		build(x << 1 | 1, mid + 1, r);
		push_up(x);
	}

	inline void update(int x, int pos, int val) {
		int l = tree[x].l, r = tree[x].r;
		if (l == r) {
			tree[x].max = max(tree[x].max, val);
			return;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid)update(x << 1, pos, val);
		else update(x << 1 | 1, pos, val);
		push_up(x);
	}

	inline int query(int x, int l, int r) {
		int le = tree[x].l, ri = tree[x].r;
		if (l <= le && ri <= r) {
			return tree[x].max;
		}
		int mid = (le + ri) >> 1;
		int maxm = 0;
		if (l <= mid) maxm = max(maxm, query(x << 1, l, r));
		if (r > mid) maxm = max(maxm, query(x << 1 | 1, l, r));
		return maxm;
	}
}

int t, n, m, a[10005], dp[10009][509];
string s;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			dp[i][j] = dp[i - 1][j - 1] + a[i];
		dp[i][0] = dp[i - 1][0];
		for (int j = 1; j <= i && j <= m; j++)
			dp[i][0] = max(dp[i][0], dp[i - j][j]);
	}
	cout << dp[n][0] << endl;
}