USACO13NOV POGO的牛 Pogo Cow

发表于

洛谷3089 BZOJ3315

  • 题意
    FJ觉得让贝西在一条直线的一维线路上进行练习，他在不同的目标点放置了$N (1 \le N \le 1000)$个目标点，目标点$i$在目标点$x_i$，该点得分为$p_i$。贝西开始时可以选择站在一个目标点上，只允许朝一个方向跳跃，从一目标点跳到另外一个目标点，每次跳跃的距离至少和上一次跳跃的距离相等，并且必须跳到一个目标点。每跳到一个目标点，贝西可以拿到该点的得分，请计算他的最大可能得分。

  • 向尔格推荐的题。长者的经验。

  • Solution

    • 首先$O(N^3)$的DP还是很好想的。而且还有很多种方法。
    • 列出一种：$f[i][j]$代表当前从第$i$个目标点开始跳，下一个跳到第$j$个目标点的最大得分。
    • 长者的经验：前（后）缀和思想，然后就可以二分答案了。
    • $f[i][j]$代表从第$i$个目标点开始跳，下一个跳到$j$或$j$之后的目标点的最大得分。
    • 然后就做完了。
    • 智障一下：只允许朝一个方向跳=向左或向右跳。
    • 我怎么这么垃圾。
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
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
	for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
	for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 1005 ;
struct node {
	int p, v ;
	friend bool operator < ( node a, node b ) {
		return a.p < b.p ;
	}
} a[maxn] ;
int n, m, f[maxn][maxn], ans ;
int find ( int x, int t ) {
	int l, r, mid, rec = n+1 ;
	l = t+1, r = n ;	
	while ( l <= r ) {
		mid = (l+r)>>1 ;	
		if ( abs(a[mid].p - a[t].p) >= abs(a[t].p - a[x].p) ) r = mid-1, rec = mid ;
		else l = mid+1 ;
	}
	return rec ;
}
void gn() {
	int i, j, k ;
	f[n][n] = f[n][n+1] = a[n].v ;
	for ( i = n-1 ; i ; i -- ) {
		f[i][n+1] = a[i].v ;	
		for ( j = n ; j > i ; j -- ) {
			k = find(i, j) ;
			f[i][j] = f[j][k] + a[i].v ;
			f[i][j] = max(f[i][j], f[i][j + 1]) ;
			ans = max(ans, f[i][j]) ;	
			//printf ( "f[%d][%d]=%d from=%d\n", i, j, f[i][j], k ) ;	
		}
	}
}
int main() {
#ifndef ONLINE_JUDGE
	freopen ( "LG3089.in", "r", stdin ) ;
	freopen ( "LG3089.out", "w", stdout ) ;
#endif
	int i, j ;
	Read(n) ;
	for ( i = 1 ; i <= n ; i ++ ) {
		Read(a[i].p) ; Read(a[i].v) ;
	}
	sort ( a+1, a+n+1 ) ;
	gn() ;
	//for ( i = 1 ; i <= n ; i ++ ) printf ( "a[%d]=%d %d\n", i, a[i].p, a[i].v ) ;
	for ( i = 1, j = n ; i < j ; i ++, j -- ) swap(a[i], a[j]) ;
	gn() ;
	printf ( "%d\n", ans ) ;
	return 0 ;
}