9.31 取数理论

题意

定义对一个长度为(N)的整数序列的({a_i})的操作为：选择序列最左(/)最右边的元素并删掉它

(A)和(B)轮流对序列(N)进行操作，由(A)先手。当只剩下一个元素(x)时，游戏结束。我们定义这次游戏的输出为(x)。(A)想让输出尽可能大，而(B)想让它尽可能小

在游戏开始之前，(A)有恰好(K)次机会对这个序列进行操作，得到一个对自己更有利的局面

当(A)与(B)都按照最优策略玩游戏时，游戏的输出值会是多少

对于每一个(K=0 o N-1)，计算答案

解法

JackAndRose的升级版

具体证明和那道题几乎一模一样

主要的难点在于对(K=0 o N-1)每一种情况都计算对应的答案

我们可以发现，一段区间的答案只与它的中心点和邻近点的取值有关（奇偶也有不同）

于是，分奇偶处理出每个中心点的答案

观察到随着区间长度的延伸，区间的中心集合是不断向两边扩展的

这启发我们利用之前求得的信息来统计新的答案

利用重复信息分奇偶转移，复杂度可以做到(O(N))

代码

（由于分了子任务，所以代码有点臃肿）

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int N, K;

int a[200100];

namespace sub1 {

int f[2010][2010][2];

int calc(int k) {
	int res = 0;
	for (int i = 0; i <= k; ++i)
		res = max(res, f[1 + i][N - k + i][0]);
	return res;	
}

void solve() {
	for (int i = 1; i <= N; ++i)  f[i][i][0] = f[i][i][1] = a[i];
	for (int i = 2; i <= N; ++i)
		for (int j = 1; j + i - 1 <= N; ++j) {
			int l = j, r = j + i - 1;
			f[l][r][0] = max(f[l + 1][r][1], f[l][r - 1][1]),
			f[l][r][1] = min(f[l + 1][r][0], f[l][r - 1][0]);
		}
	
	if (K != -1)
		printf("%d
", calc(K));
	else {
		for (int i = 0; i < N; ++i)  
			printf("%d%c", calc(i), " 
"[i == N - 1]);	
	}
}

}

namespace sub2 {

int f[200100], g[200100], ans[200100];

void solve() {
	
	f[1] = a[1], f[N] = a[N];
	for (int i = 2; i < N; ++i) {
		int tmp = max(a[i - 1], max(a[i], a[i + 1]));
		if (a[i] == tmp)
			f[i] = max(a[i - 1], a[i + 1]);
		else
			f[i] = a[i];	
	}
	
	for (int i = 1; i < N; ++i)
		g[i] = max(a[i], a[i + 1]);
	
	if (N & 1) { 
	
		int l = (N + 1) / 2, r = (N + 1) / 2, sum = f[l];
		ans[0] = sum;
	
		for (int i = 2; i < N; i += 2) {
			l--, r++;
			sum = max(sum, max(f[l], f[r]));	
			ans[i] = sum;
		} 
	
		l = N / 2, r = N / 2 + 1, sum = 0;
		for (int i = 1; i < N; i += 2) {
			sum = max(sum, max(g[l], g[r]));
			l--, r++;
			ans[i] = sum;
		}
	} else {
		
		int l = N / 2, r = N / 2, sum = g[l];
		ans[0] = sum;
				
		for (int i = 2; i < N; i += 2) {
			l--, r++;
			sum = max(sum, max(g[l], g[r]));
			ans[i] = sum;
		}
		
		l = N / 2, r = N / 2 + 1, sum = 0;
		for (int i = 1; i < N; i += 2) {
			sum = max(sum, max(f[l], f[r]));
			l--, r++;
			ans[i] = sum;	
		}
	}
	
	ans[N - 1] = *max_element(a + 1, a + N + 1);
	
	if (K == -1)
		for (int i = 0; i < N; ++i)  printf("%d%c", ans[i], " 
"[i == N - 1]);	
	else
		printf("%d
", ans[K]);
	
}
}

int main() {
	
//	freopen("game.in", "r", stdin);
//	freopen("game.out", "w", stdout);
	
	scanf("%d%d", &N, &K);
	
	for (int i = 1; i <= N; ++i)  scanf("%d", a + i);
	
	if (N <= 2000) 
		sub1::solve();
	else
		sub2::solve();
	
	return 0;
}