USACO08JAN跑步Running

发表于

洛谷1353 POJ3661

  • 题意
    有$n ( 1 \le n \le 10000 )$分钟时间跑步，第$i$分钟跑$d_i (1 \le d_i \le 1000)$米。每一分钟如果跑步的话疲劳度增加1,休息的话减少1,而且休息必须到疲劳度为0才能重新开始。疲劳度到0后可以继续休息，但是疲劳度还是0，疲劳度不能超过$m ( 1 \le m \le 500)$.求最长能跑多远。
  • Solution
    • 简单DP。设$f[i][j][0/1]$代表第$i$分钟疲劳度为$j$时跑(0)和不跑(1)时能跑的最远距离。转移的时候注意一下细节就行了。
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
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void Read ( LL &x, char c = getchar() ) {
	for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
	for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const LL maxn = 1e4+5, maxm = 505 ;
LL n, m, f[maxn][maxm][2], d[maxn] ;
int main() {
#ifndef ONLINE_JUDGE
	freopen ( "LG1353.in", "r", stdin ) ;
	freopen ( "LG1353.out", "w", stdout ) ;
#endif
	LL i, j ;
	Read(n) ; Read(m) ;
	for ( i = 1 ; i <= n ; i ++ ) Read(d[i]) ;
	f[1][0][0] = 0 ;
	f[1][1][1] = d[1] ;
	for ( i = 2 ; i <= n ; i ++ ) {
		for ( j = 1 ; j <= m ; j ++ ) {
			f[i][j][0] = max(f[i - 1][j + 1][0], f[i - 1][j + 1][1]) ;
			f[i][j][1] = f[i - 1][j - 1][1] + d[i] ;
			if ( j == 1 ) f[i][j][1] = max(f[i][j][1], f[i - 1][j - 1][0] + d[i]) ;
		}
		f[i][0][0] = max(f[i - 1][0][0], f[i - 1][1][1]) ;
		f[i][0][0] = max(f[i][0][0], f[i - 1][1][0]) ;
	}
	printf ( "%lld\n", f[n][0][0] ) ;	
	return 0 ;
}