POI2009 KON-Ticket Inspector

题目链接

Description

一辆火车依次经过 (n) 个车站，顺序是 (1, 2, 3, ..., n - 1, n)。给定 (A_{i, j}) 表示从 (i) 站上车，(j) 站下车的个数。

有 (K) 次在每站操作后的检票机会，问最多能检票的多少不同的人。

Solution

这相当于给你 (dfrac{n^2}{2}) 条线段（对于 (A_{i, j}) 而言对应的线段是 ([i, j - 1])，因为选的点是在那站后，下车的就没了），每个线段有个权值，让你选择 (K) 个点，使得 (K) 个点所涉及的线段（重复的算一次）的权值和最大。

考虑 DP，用代表元计数法，考虑把每个线段的贡献记录在他那条线段上有的第一个点上。

状态设计

设 (f_{i, j}) 为前 (i) 个车站，已经检票了 (j) 次，并且在第 (i) 个车站后检票的最多人数

初始状态

(f_{0, 0} = 0)，其余为负无穷（其实这里赋值与否没啥关系）。

状态转移

(f_{i, j} = max{f_{k, j - 1} + val(k + 1, i)})

其中 (val(l, r)) 表示在线段左端点在 ([l, r]) 且右端点 $ ge r$ 的线段个数，这个东西可以 (O(N^3)) 暴力预处理。

答案

(ans = max{f[i][K]})

时间复杂度

(O(N^2K))

Tips

• 大坑，可能造成贡献的点 $ < K$，这时候你就需要从剩下的站点中，选择一些字典序较小的来输出。

Code

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 605, S = 55;

int n, tot, K, a[N][N], pre[N][S], val[N][N], cnt[N], f[N][S];

bool vis[N];

void print(int i, int j) {
	if (j == 0 || i == 0) return ;
	print(pre[i][j], j - 1);
	vis[i] = true;
	++tot;
}

int main() {
	scanf("%d%d", &n, &K);
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) scanf("%d", &a[i][j]);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) cnt[j] = 0;
		for (int j = i; j <= n; j++) {
			for (int k = j + 1; k <= n; k++) cnt[k - 1] += a[j][k];
			for (int k = n; k >= j; k--) val[i][j] += cnt[k];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= K; j++) {
			for (int k = 0; k < i; k++) {
				if (f[k][j - 1] + val[k + 1][i] > f[i][j]) {
					f[i][j] = f[k][j - 1] + val[k + 1][i];
					pre[i][j] = k;
				}
			}

		}
	}

	int ans = 0, p;
		for (int i = 1; i <= n; i++) if (f[i][K] > ans) ans = f[i][K], p = i;
	print(p, K);
	for (int i = 1; i <= n; i++) {
		if (vis[i]) printf("%d ", i);
		else if (tot < K) tot++, printf("%d ", i);
	}
	return 0;
}