[POI2009]KON-Ticket Inspector 题解

lizhous · 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]);
    }
}