UVa 12209 Foot Notes

题目描述

给定一篇包含 $N$ 行的文章，以及 $W$ 个关键词，每个关键词出现在若干行中。我们需要将文章分成若干连续行段，每个行段作为一页。每一页可以容纳最多 $S$ 行正文（即文章行）和若干脚注。若某页中包含了某个关键词，则该页必须为该关键词添加一个脚注（同一关键词在一页中只需一个脚注）。每页的总开销为：正文行数 + 该页出现的不同关键词个数，该值不能超过 $S$。

目标是最小化所有页的脚注总数（即所有页中不同关键词出现次数之和）。如果无法将整篇文章安排成若干页（即任何划分都会导致某页超载），则输出 -1。

输入格式

第一行包含整数 $T$（$1\le T\le 35$），表示测试用例数。
每个测试用例的第一行包含三个整数 $N,S,W$（$1\le N\le 500$，$1\le S\le 100$，$0\le W\le 100$），分别表示文章行数、每页最大容纳行数、关键词数量。
接下来 $W$ 行，每行描述一个关键词的出现位置。每行以整数 $K_i$（$1\le K_i\le N$）开头，表示该关键词出现的次数，后面跟着 $K_i$ 个整数，表示该关键词出现的行号（行号在 $1$ 到 $N$ 之间，可能重复，但实际位置唯一，输入保证合法）。

输出格式

对于每个测试用例，输出一行 Case x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最小脚注总数；若无法安排，则输出 Case x: -1。

样例

输入

3
5 5 3
2 1 2
2 3 4
1 5
5 2 3
2 1 2
2 3 4
1 5
1 1 1
1 1

输出

Case 1: 3
Case 2: 5
Case 3: -1

题目分析

本题本质上是一个序列分段最优化问题：将 $1\dots N$ 的有序行号划分成若干连续区间（页），每页的“重量”由该页内出现的不同关键词个数决定，且正文行数加该重量不能超过容量 $S$。总代价为所有页的重量之和，求最小总代价。

直接枚举所有划分方案是指数级的，不可行。但注意到 $N$ 只有 $500$，我们可以考虑动态规划。

设 $\text{dp}[i]$ 表示处理完前 $i$ 行（即第 $1$ 到第 $i$ 行已经分好页），且第 $i$ 行正好是一页的结尾时，所需的最小脚注总数。那么答案就是 $\text{dp}[N]$。

转移时，枚举上一页的结尾 $j$（$0\le j<i$），则当前页为区间 $[j+1,i]$，长度为 $\text{len}=i-j$，该页内不同关键词个数记为 $\text{foot}(j+1,i)$。若 $\text{len}+\text{foot}(j+1,i)\le S$，则可以转移：
$$\text{dp}[i]=\min (\text{dp}[i],\text{dp}[j]+\text{foot}(j+1,i))$$

初始 $\text{dp}[0]=0$，其余为无穷大。最终若 $\text{dp}[N]$ 仍为无穷大，则输出 -1。

因此问题的核心在于快速计算任意区间 $[l,r]$ 内不同关键词的个数 $\text{foot}(l,r)$。

解题思路

预处理区间内不同关键词个数

由于 $N\le 500$，我们可以预处理所有 $N(N+1)/2$ 个区间的 $\text{foot}$ 值。具体做法：

• 对于每个左端点 $l$，从左到右扩展右端点 $r$，维护一个布尔数组（大小为 $W+1$）记录哪些关键词已经在该区间内出现过。每扩展一行 $r$，将该行所有出现的关键词标记为已见，并累加计数。
• 这样，在 $O(N^2\cdot \text{每行关键词平均数})$ 的时间内即可得到所有 $\text{foot}[l][r]$。最坏情况下每行包含所有 $W$ 个关键词，则复杂度为 $O(N^2\cdot W)$，即 $500^2\times 100=25\times 10^6$，完全可行。

动态规划

得到 $\text{foot}$ 表后，直接套用上述 $\text{DP}$ 即可。转移时，由于每页最多 $S$ 行（$S\le 100$），实际上 $j$ 只需枚举 $[i-S,i-1]$ 的范围，进一步优化常数。

边界情况处理

• 当 $W=0$ 时，所有 $\text{foot}=0$，只需保证每页行数不超过 $S$，显然总有解（因为 $S\ge 1$），答案为 $0$。
• 当 $S=1$ 时，只有长度为 $1$ 的页可行，且该页不能包含任何关键词，否则 $1+\text{foot}>1$。因此若存在某行含有关键词，则无法安排，输出 -1。

复杂度分析

• 预处理 $\text{foot}$：$O(N^2\cdot W)$，此处 $N\le 500,W\le 100$，约为 $2.5\times 10^7$ 次操作，在时限内。
• 动态规划：$O(N\cdot S)$，因为每层最多枚举 $S$ 个 $j$，$S\le 100$，非常小。
• 空间复杂度：$O(N^2)$ 存储 $\text{foot}$，也可优化为只存储一维，但 $500^2$ 仅 $250000$，无压力。

代码实现

// Foot Notes
// UVa ID: 12209
// Verdict: Accepted
// Submission Date: 2026-06-21
// UVa Run Time: 0.100s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

int main() {
int T;
scanf("%d", &T);
for (int tc = 1; tc <= T; ++tc) {
int N, S, W;
scanf("%d%d%d", &N, &S, &W);
vector<int> lineWords[N + 1]; // 每行出现的关键词编号
for (int id = 1; id <= W; ++id) {
int K;
scanf("%d", &K);
for (int t = 0; t < K; ++t) {
int x;
scanf("%d", &x);
lineWords[x].push_back(id);
}
}

// 预处理 foot[l][r]：区间[l,r]内不同关键词个数
vector<vector<int>> foot(N + 1, vector<int>(N + 1, 0));
for (int l = 1; l <= N; ++l) {
vector<bool> seen(W + 1, false);
int cur = 0;
for (int r = l; r <= N; ++r) {
for (int id : lineWords[r])
if (!seen[id]) {
seen[id] = true;
++cur;
}
foot[l][r] = cur;
}
}

const int INF = 1e9;
vector<int> dp(N + 1, INF);
dp[0] = 0;
for (int i = 1; i <= N; ++i)
for (int j = max(0, i – S); j < i; ++j) {
int len = i – j;
int f = foot[j + 1][i];
if (len + f <= S)
dp[i] = min(dp[i], dp[j] + f);
}

if (dp[N] >= INF)
printf("Case %d: -1\\n", tc);
else
printf("Case %d: %d\\n", tc, dp[N]);
}
return 0;
}

总结

本题是一道典型的序列分段 $\text{DP}$，关键点在于预处理区间内不同元素个数。由于 $N$ 范围较小，可以直接 $O(N^{2}W)$ 预处理，再配合线性 $\text{DP}$ 得到最优解。

技巧总结：

• 当 $N$ 较小（$\le 500$）时，预处理所有区间信息是常用手段。
• 注意每页的容量约束，限制转移范围，提高效率。
• 边界情况（$W=0$ 或 $S$ 很小）需特别考虑，避免错误输出。

本题代码简洁，思路清晰，适合作为区间 $\text{DP}$ 的入门练习。