自动搬运

查看原文

来自洛谷，原作者为

	lizhous zxq

搬运于2025-08-24 21:49:27，当前版本为作者最后更新于2022-10-10 21:47:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[POI2009]KON-Ticket Inspector 题解

传送门

分析

我们发现有些人可能重复检票，统计十分麻烦，所以正难则反，我们求未被检票的人最少有几个。

设 $f_{i,z}$ 表示在站 $i$ 检票，共检票 $z$ 次的最少未检票人数。枚举上次检票的位置 $la$，答案就是 $f_{la,z-1}$ 加上中间漏掉的人数，即这两个站之间上过并下过车的人数。我们发现时间复杂度已经 $O(n^2k)$，所以求人数需要 $O(1)$。

考虑预处理前缀和，设 $sum_{i,z}$ 表示在站 $i,z$ 之间上过且下过车的人数，放到二维数组中考虑。根据输入，$a_{i,z}$ 表示在 $i$ 上车，$z$ 下车。我们发现他会对 $sum_{j,k}$ 做出贡献，当且仅当 $j\le i$ 且 $k\ge z$，前缀和即可。

细节：在统计时，记得加上这站后上车的人数，他们也检不到票。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n, k, las[701][101], dp[701][101], a[701][701], fun[701], sum[701][701];
signed main() {
	scanf("%lld%lld", &n, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			scanf("%lld", &a[i][j]);
			sum[i][j] = a[i][j];
		}
	}
    //前缀和
	for (int i = 1; i <= n; i++) {
		for (int z = i + 1; z <= n; z++) {
			sum[i][z] += sum[i][z - 1];
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int z = i + 1; z <= n; z++) {
			sum[i][z] += sum[i + 1][z];
		}
	}
	memset(dp, 127, sizeof(dp));
	for (int i = 1; i <= n; i++) { //当前站点
		dp[i][1] = sum[1][i];
		las[i][1] = -1;
		for (int z = 2; z <= k; z++) { //检票次数
			for (int la = 1; la < i; la++) { //上次检票站
				if (dp[la][z - 1] + sum[la + 1][i] < dp[i][z]) {
					dp[i][z] = dp[la][z - 1] + sum[la + 1][i]; //转移
					las[i][z] = la; //记录上次检票站点
				}
			}
		}
	}
	int ans = 10000000000;
	int it = n, cnt = k;
	for (int i = 1; i <= n; i++) {
		if (dp[i][k] + sum[i + 1][n] < ans) { //统计答案
			it = i;
			ans = dp[i][k] + sum[i + 1][n];
		}
	}
	while (it != -1) { //跳站点
		fun[cnt] = it;
		it = las[it][cnt--];
	}
	for (int i = 1; i <= k; i++) { //倒序输出
		printf("%lld ", fun[i]);
	}
}