算法竞赛入门经典(第二版)-刘汝佳-第九章动态规划初步例题（11/31）

本文主要是介绍算法竞赛入门经典(第二版)-刘汝佳-第九章动态规划初步例题（11/31），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

说明
例题
- 例9-1 UVA 1025 地铁里的间谍
- 例9-2 UVA 437 巴比伦塔
- 例9-3 UVA 1347 旅游（未尝试）
- 例9-4 UVA 116 单向DSP
- 例9-5 UVA 12563 劲歌金曲
- 例9-6 UVA 11400 照明系统设计（未尝试）
- 例9-7 UVA 11584 划分为回文串
- 例9-8 UVA 1625 颜色的长度
- 例9-9 UVA 10003 切木棍
- 例9-10 UVA 1626 括号系列
- 例9-11 UVA 1331 最大面积最小的三角剖分（未尝试）
- 例9-12 UVA 12186 工人的请愿书
- 例9-13 UVA 1220 Hali-Bula的晚会
- 例9-14 UVA 1218 完美的服务
- 例9-15 UVA 10817 校长的烦恼
- 例9-16 UVA 1252 20个问题（其后皆未尝试）
- 例9-17 UVA 1412 基金管理
- 例9-18 UVA 10618 跳舞机
- 例9-19 UVA 1627 团队分组
- 例9-20 UVA 10934 装满水的气球
- 例9-21 UVA 1336 修长城
- 例9-22 UVA 12105 越大越好
- 例9-23 UVA 1204 有趣的游戏
- 例9-24 UVA 12099 书架
- 例9-25 UVA 12170 轻松爬山
- 例9-26 UVA 1380 一个调度问题
- 例9-27 UVA 10559 方块消除
- 例9-28 UVA 1439 独占访问
- 例9-29 UVA 1228 整数传输
- 例9-30 UVA 1375 给孩子起名
- 例9-31 UVA 1628 送披萨

说明

本文是我对第9章31道例题的练习总结，建议配合紫书——《算法竞赛入门经典（第2版）》阅读本文。
另外为了方便做题，我在VOJ上开了一个contest，欢迎一起在上面做：
第九章例题contest（1）
第九章例题contest（2）
如果想直接看某道题，请点开目录后点开相应的题目！！！

例题

例9-1 UVA 1025 地铁里的间谍

题意
某城市的地铁是线性的，有n（2≤n≤50）个车站，从左到右编号为1～n。有M1辆列车从第1站开始往右开，还有M2辆列车从第n站开始往左开。在时刻0，Mario从第1站出发，目的是在时刻T（0≤T≤200）会见车站n的一个间谍。在车站等车时容易被抓，所以她决定尽量躲在开动的火车上，让在车站等待的总时间尽量短。列车靠站停车时间忽略不计，且Mario身手敏捷，即使两辆方向不同的列车在同一时间靠站，Mario也能完成换乘。
输入第1行为n，第2行为T，第3行有n－1个整数t1, t2, … , tn－1（1≤ti≤70），其中ti表示地铁从车站i到i＋1的行驶时间（两个方向一样）。第4行为M1（1≤M1≤50），即从第1站出发向右开的列车数目。第5行包含M1个整数d1, d2,…, dM1（0≤di≤250，di＜di＋1），即各列车的出发时间。第6、7行描述从第n站出发向左开的列车，格式同第4、5行。输出仅包含一行，即最少等待时间。无解输出impossible。

思路
时间是单向流逝的，是一个天然的“序”。影响到决策的只有当前时间和所处的车站，所以可以用d(i,j)表示时刻i，你在车站j（编号为1～n），最少还需要等待多长时间。边界条件是d(T,n)=0，其他d(T,i)（i不等于n）为正无穷。有如下3种决策。

决策1：等1分钟。
决策2：搭乘往右开的车（如果有）。
决策3：搭乘往左开的车（如果有）。

代码中有一个has_train数组，其中has_train[t][i][0]表示时刻t，在车站i是否有往右开的火车，has_train[t][i][1]类似，不过记录的是往左开的火车。这个数组不难在输入时计算处理，详见代码。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 51;
const int M = 51;
const int T = 201;
const int INF = 100000000;int n, tmax, m[2];
int t[N], sum[2][N], d[2][M];
bool has_train[T][N][2];
int dp[T][N];int main(void)
{int kase = 0;while (scanf("%d", &n) && n) {scanf("%d", &tmax);sum[0][1] = 0;for (int i = 1; i < n; i++) {scanf("%d", &t[i]);sum[0][i+1] = sum[0][i]+t[i];}sum[1][n] = 0;for (int i = n-1; i >= 1; i--)sum[1][i] = sum[1][i+1]+t[i];memset(has_train, 0, sizeof(has_train));for (int j = 0; j < 2; j++) {scanf("%d", &m[j]);for (int k = 0; k < m[j]; k++) {scanf("%d", &d[j][k]);for (int i = 1; i <= n; i++) {if (sum[j][i]+d[j][k] <= tmax)has_train[sum[j][i]+d[j][k]][i][j] = 1;}}}for (int j = 1; j < n; j++)dp[tmax][j] = INF;dp[tmax][n] = 0;for (int i = tmax-1; i >= 0; i--) {for (int j = 1; j <= n; j++) {dp[i][j] = dp[i+1][j] + 1;if (j < n && has_train[i][j][0] && i+t[j] <= tmax)dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]);if (j > 1 && has_train[i][j][1] && i+t[j-1] <= tmax)dp[i][j] = min(dp[i][j], dp[i+t[j-1]][j-1]);}}printf("Case Number %d: ", ++kase);if (dp[0][1] >= INF) printf("impossible\n");else printf("%d\n", dp[0][1]);}return 0;
}

例9-2 UVA 437 巴比伦塔

题意
有n（n≤30）种立方体，每种都有无穷多个。要求选一些立方体摞成一根尽量高的柱子（可以自行选择哪一条边作为高），使得每个立方体的底面长宽分别严格小于它下方立方体的底面长宽。

思路
在任何时候，只有顶面的尺寸会影响到后续决策，因此可以用二元组(a,b)来表示“顶面尺寸为 a* b”这个状态。因为每次增加一个立方体以后顶面的长和宽都会严格减小，所以这个图是DAG，可以套用前面学过的DAG最长路算法。
这个算法没问题，不过落实到程序上时会遇到一个问题：不能直接用d(a,b)表示状态值，因为a和b可能会很大。怎么办呢？可以用(idx, k)这个二元组来“间接”表达这个状态，其中idx为顶面立方体的序号，k是高的序号（假设输入时把每个立方体的3个维度从小到大排序，编号为0～2）。例如，若立方体3的大小为abc（其中a≤b≤c），则状态(3,1)就是指这个立方体在顶面，且高是b（因此顶面大小为a*c）。因为idx是0～n－1的整数，k是0～2的整数，所以可以很方便地用二维数组来存取。状态总数是O(n)的，每个状态的决策有O(n)个，时间复杂度为O(n^2)。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 31;struct Node {int h[3], v;bool operator < (const Node& b) const{return v < b.v;}
};int n;
Node a[N];
int dp[N][3];int dag(int i, int j)
{int& ans = dp[i][j];if (ans > 0) return ans;ans = a[i].h[j];int x = (j == 0) ? a[i].h[1] : a[i].h[0];int y = (j == 2) ? a[i].h[1] : a[i].h[2];for (int i1 = 0; i1 < n; i1++) {for (int j1 = 0; j1 < 3; j1++) {int x1 = (j1 == 0) ? a[i1].h[1] : a[i1].h[0];int y1 = (j1 == 2) ? a[i1].h[1] : a[i1].h[2];if (x < x1 && y < y1) ans = max(ans, dag(i1, j1)+a[i].h[j]);}}return ans;
}int main(void)
{int kase = 0;while (scanf("%d", &n) && n) {for (int i = 0; i < n; i++) {Node& t = a[i];scanf("%d%d%d", &t.h[0], &t.h[1], &t.h[2]);sort(t.h, t.h+3);t.v = t.h[0]*t.h[1]*t.h[2];}sort(a, a+n);memset(dp, 0, sizeof(dp));int res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < 3; j++) {res = max(res, dag(i, j)); } }printf("Case %d: maximum height = %d\n", ++kase, res);}return 0;
}

例9-3 UVA 1347 旅游（未尝试）

题意

思路

代码

例9-4 UVA 116 单向DSP

题意
给一个m行n列（m≤10，n≤100）的整数矩阵，从第一列任何一个位置出发每次往右、右上或右下走一格，最终到达最后一列。要求经过的整数之和最小。整个矩阵是环形的，即第一行的上一行是最后一行，最后一行的下一行是第一行。输出路径上每列的行号。多解时输出字典序最小的。图9-5中是两个矩阵和对应的最优路线（唯一的区别是最后一行）。

思路
在这个题目中，每一列就是一个阶段，每个阶段都有3种决策：直行、右上和右下。
有了前面的经验，不难设计出状态：设d(i,j)为从格子(i,j)出发到最后一列的最小开销。但是本题不仅要输出解，还要求字典序最小，这就需要在计算d(i,j)的同时记录“下一列的行号”的最小值（当然是在满足最优性的前提下），细节参见代码。
注意：这个题目不能设d(i,j)为从第一列出发到格子(i,j)的最小开销，这样决策将无法保证输出的结果是字典序最小的。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;const int N = 11;
const int M = 101;int n, m;
int a[N][M];
int dp[2][N];
int next[N][M];int main()
{while (scanf("%d%d", &n, &m) != EOF) {for (int i = 0; i < n; i++) {for (int j = 0; j < m ; j++) {scanf("%d", &a[i][j]); } }memset(dp, 0, sizeof(dp));for (int j = m-1; j >= 0; j--) {int k1 = j&1, k0 = (j+1)&1;for (int i = 0; i < n; i++) {dp[k1][i] = dp[k0][i]+a[i][j];next[i][j] = i;}if (n > 1) {for (int i = 0; i < n; i++) {int i1 = (i-1+n)%n, tmp = dp[k0][i1]+a[i][j];if (tmp < dp[k1][i] || tmp == dp[k1][i] && i1 < next[i][j]) {dp[k1][i] = tmp;next[i][j] = i1;}}}if (n > 2) {for (int i = 0; i < n; i++) {int i1 = (i+1)%n, tmp = dp[k0][i1]+a[i][j];if (tmp < dp[k1][i] || tmp == dp[k1][i] && i1 < next[i][j]) {dp[k1][i] = tmp;next[i][j] = i1;}}}}int res = dp[0][0], idm = 0;for (int i = 0; i < n; i++) {if (dp[0][i] < res) {res = dp[0][i];idm = i;}}printf("%d", idm+1);for (int j = 0; j < m-1; j++) {printf(" %d", next[idm][j]+1);idm = next[idm][j];}printf("\n%d\n", res);}return 0;
}

例9-5 UVA 12563 劲歌金曲

题意
如果问一个麦霸：“你在KTV里必唱的曲目有哪些？”得到的答案通常都会包含一首“神曲”：古巨基的《劲歌金曲》。为什么呢？一般来说，KTV不会在“时间到”的时候鲁莽地把正在唱的歌切掉，而是会等它放完。例如，在还有15秒时再唱一首2分钟的歌，则实际上多唱了105秒。但是融合了37首歌曲的《劲歌金曲》长达11分18秒(5)，如果唱这首，相当于多唱了663秒！
假定你正在唱KTV，还剩t秒时间。你决定接下来只唱你最爱的n首歌（不含《劲歌金曲》）中的一些，在时间结束之前再唱一个《劲歌金曲》，使得唱的总曲目尽量多（包含《劲歌金曲》），在此前提下尽量晚的离开KTV。
输入n（n≤50），t（t≤10^9）和每首歌的长度（保证不超过3分钟(6)），输出唱的总曲目以及时间总长度。输入保证所有n＋1首曲子的总长度严格大于t。

思路
虽说t≤10^9，但由于所有n＋1首曲子的总长度严格大于t，实际上t不会超过180n＋678。这样就可以转化为0-1背包问题了。
dp[i][j]表示第i首歌做出选择（唱或者不唱）情况下总时间为j时所能唱的最多歌曲数量（这是首要最大化的结果）。输出答案时在最多歌曲数量的选择中，找出唱歌总时间最多的那个就是答案了。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;const int N = 51;
const int JGJQ = 678;
const int MAX = 180*N;int n, t;
int a[N];
int dp[2][MAX];int main()
{int kase;scanf("%d", &kase);for (int k = 1; k <= kase; k++) {scanf("%d%d", &n, &t);for (int i = 0; i < n; i++)scanf("%d", &a[i]);memset(dp, -1, sizeof(dp));dp[1][0] = 0;int ans = 0;for (int i = 0; i < n; i++) {int k1 = i&1, k0 = (i+1)&1;for (int j = 0; j < t; j++) {dp[k1][j] = dp[k0][j];if (j >= a[i] && dp[k0][j-a[i]] >= 0)dp[k1][j] = max(dp[k1][j], dp[k0][j-a[i]] + 1);ans = max(ans, dp[k1][j]);}}int len = 0;for (int j = 0; j < t; j++)if (dp[(n-1)&1][j] == ans) len = j;printf("Case %d: %d %d\n", k, ans+1, len+JGJQ);}return 0;
}

例9-6 UVA 11400 照明系统设计（未尝试）

题意

思路

代码

例9-7 UVA 11584 划分为回文串

题意
输入一个由小写字母组成的字符串，你的任务是把它划分成尽量少的回文串。例如，racecar本身就是回文串；fastcar只能分成7个单字母的回文串，aaadbccb最少分成3个回文串：aaa, d, b ccb。字符串长度不超过1000。

思路
d[i]为字符0～i划分成的最小回文串的个数，则d[i] = min{d[j] ＋ 1 | s[j＋1～i]是回文串}。注意频繁的要判断回文串。状态O(n)个，决策O(n)个，如果每次转移都需要O(n)时间判断，总时间复杂度会达到O(n^3)。
可以先用O(n^{2)时间预处理s[i…j]是否为回文串。方法是枚举中心，然后不断向左右延伸并且标记当前子串是回文串，直到延伸的左右字符不同为止(7)。这样一来，每次转移的时间降为了O(1)，总时间复杂度为O(n}2)。

实际上就是要做两次DP。第一次DP预处理原串的子串是否是回文串（dp[i][j]表示长度为i、起点为j的子串是否是回文串），第二次DP找出将字符0～i划分成的最小回文串的个数（用d[i]表示）。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 1001;int n;
char s[N];
bool dp[N][N];
int d[N];int main(void)
{int kase;scanf("%d", &kase);while (kase--) {scanf("%s", s);n = strlen(s);memset(dp, 1, sizeof(dp));for (int j = 0; j < n; j++)dp[1][j] = 1;for (int i = 2; i <= n; i++) {for (int j = 0; j <= n-i; j++) {if (s[j] == s[j+i-1] && dp[i-2][j+1])dp[i][j] = 1;elsedp[i][j] = 0;}}d[0] = 0;for (int k = 1; k <= n; k++) {d[k] = k;for (int i = 0; i < k; i++)if (dp[k-i][i]) d[k] = min(d[k], d[i]+1);}printf("%d\n", d[n]);}return 0;
}

例9-8 UVA 1625 颜色的长度

题意
输入两个长度分别为n和m（n,m≤5000）的颜色序列，要求按顺序合并成同一个序列，即每次可以把一个序列开头的颜色放到新序列的尾部。
例如，两个颜色序列GBBY和YRRGB，至少有两种合并结果：GBYBRYRGB和YRRGGBBYB。对于每个颜色c来说，其跨度L©等于最大位置和最小位置之差。
你的任务是找一种合并方式，使得所有L©的总和最小。

思路
根据前面的经验，可以设d(i,j)表示两个序列已经分别移走了i和j个元素，还需要多少费用。等一下！什么叫“还需要多少费用”呢？本题的指标函数（即需要最小化的函数）比较复杂。当某颜色第一次出现在最终序列中时，并不知道它什么时候会结束；而某个颜色的最后一个元素已经移到最终序列里时，又“忘记”了它是什么时候第一次出现的。
怎么办呢？如果记录每个颜色的第一次出现位置，状态会变得很复杂，时间也无法承受，所以只能把在指标函数的“计算方式”上想办法：不是等到一个颜色全部移完之后再算，而是每次累加。换句话说，当把一个颜色移到最终序列前，需要把所有“已经出现但还没结束”的颜色的L©值加1。更进一步地，因为并不关心每个颜色的L©，所以只需要知道有多少种颜色已经开始但尚未结束。
例如，序列GBBY和YRRGB，分别已经移走了1个和3个元素（例如，已经合并成了YRRG）。下次再从序列2移走一个元素（即G）时，Y和G需要加1。下次再从序列1移走一个元素（它是B）时，只有Y需要加1（因为G已经结束）。
这样，可以事先算出每个颜色在两个序列中的开始和结束位置，就可以在动态规划时在O(1)时间内计算出状态d(i,j)中“有多少个颜色已经出现但尚未结束”，从而在O(1)时间内完成状态转移。状态总是为O(nm)个，总时间复杂度也是O(nm)。

做完后的感想：
这个题目的确如书中所说，思路比较清晰，但是做起来细节的问题很多，容易出错。尤其需要注意的是，这个题目dp(i, j)中i和j的范围应该分别是0_n以及0m，而不是0_n-1和0m-1。我在这个地方思路陷进去了，代码一直错。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 5001;int n[2];
char s[2][N];
int id[26][2][2];
int a[N][N], dp[N][N];int main(void)
{int kase;scanf("%d", &kase);while (kase--) {for (int i = 0; i < 2; i++) {scanf("%s", s[i]);n[i] = strlen(s[i]);for (int j = 0; j < 26; j++) {id[j][i][0] = N; id[j][i][1] = -1;}for (int j = 0; s[i][j]; j++) {int k = s[i][j]-'A';id[k][i][0] = min(id[k][i][0], j);id[k][i][1] = max(id[k][i][1], j);}}for (int i = 0; i <= n[0]; i++) {for (int j = 0; j <= n[1]; j++) {int cnt = 0;for (int r = 0; r < 26; r++) {if ( (id[r][0][0] < i || id[r][1][0] < j)&& (i <= id[r][0][1] || j <= id[r][1][1]) )cnt++;}a[i][j] = cnt;//printf("i=%d, j=%d, cnt=%d\n", i, j, cnt);}}dp[0][0] = 0;for (int i = 0; i <= n[0]; i++) {for (int j = 0; j <= n[1]; j++) {if (i || j) dp[i][j] = N*N;if (i) dp[i][j] = min(dp[i][j], dp[i-1][j] + a[i-1][j]);if (j) dp[i][j] = min(dp[i][j], dp[i][j-1] + a[i][j-1]);//printf("i=%d, j=%d, dp=%d\n", i, j, dp[i][j]);}}printf("%d\n", dp[n[0]][n[1]]);}return 0;
}

例9-9 UVA 10003 切木棍

题意
有一根长度为L（L＜1000）的棍子，还有n（n＜50）个切割点的位置（按照从小到大排列）。你的任务是在这些切割点的位置处把棍子切成n＋1部分，使得总切割费用最小。每次切割的费用等于被切割的木棍长度。例如，L=10，切割点为2, 4, 7。如果按照2, 4, 7的顺序，费用为10＋8＋6=24，如果按照4, 2, 7的顺序，费用为10＋4＋6=20。

思路
设d(i,j)为切割小木棍i～j的最优费用，则，其中最后一项a[j]－a[i]代表第一刀的费用。切完之后，小木棍变成i～k和k～j两部分，状态转移方程由此可得。把切割点编号为1～n，左边界编号为0，右边界编号为n＋1，则答案为d(0,n＋1)。
状态有O(n^{2)个，每个状态的决策有O(n)个，时间复杂度为O(n}3)。
值得一提的是，本题可以用四边形不等式优化到O(n^2)，见《算法竞赛入门经典——训练指南》或其他参考资料。（当然这个我还没有研究）

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 52;
const int M = 1000;int len, n;
int a[N];
int dp[N][N];int main(void)
{while (scanf("%d", &len) && len) {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);a[0] = 0;a[n+1] = len;memset(dp, 0, sizeof(dp));for (int i = 2; i <= n+1; i++) {for (int j = 0; j <= n+1-i; j++) {dp[i][j] = M*N;for (int k = 1; k <= i-1; k++)dp[i][j] = min(dp[i][j], dp[k][j]+dp[i-k][j+k]+a[j+i]-a[j]);}}printf("The minimum cutting is %d.\n", dp[n+1][0]);}return 0;
}

例9-10 UVA 1626 括号系列

题意
定义如下正规括号序列（字符串）：

空序列是正规括号序列。
如果S是正规括号序列，那么(S)和[S]也是正规括号序列。
如果A和B都是正规括号序列，那么AB也是正规括号序列。

例如，下面的字符串都是正规括号序列：()，[]，(())，([])，()[]，()[()]，而如下字符串则不是正规括号序列：(，[，]，)(，([()。
输入一个长度不超过100的，由“(”、“)”、“[”、“]”构成的序列，添加尽量少的括号，得到一个规则序列。如有多解，输出任意一个序列即可。

思路
设串S至少需要增加d(S)个括号，转移如下：

如果S形如(S′)或者[S′]，转移到d(S′)。
如果S至少有两个字符，则可以分成AB，转移到d(A)＋d(B)。

边界是：S为空时d(S)=0，S为单字符时d(S)=1。注意(S′, [S′, ) S′之类全部属于第二种转移，不需要单独处理。
注意：不管S是否满足第一条，都要尝试第二种转移，否则“[][]”会转移到“][”，然后就只能加两个括号了。
当然，上述“方程”只是概念上的，落实到程序时要改成子串在原串中的起始点下标，即用d(i,j)表示子串S[i～j]至少需要添加几个括号。下面是递推写法，比记忆化写法要快好几倍，而且代码更短。要注意状态的枚举顺序。
本题需要打印解，但是上面的代码只计算了d数组，如何打印解呢？可以在打印时重新检查一下哪个决策最好。这样做的好处是节约空间，坏处是打印时代码较复杂，速度稍慢，但是基本上可以忽略不计（因为只有少数状态需要打印）。
本题唯一的陷阱是：输入串可能是空串，因此不能用scanf("%s", s)的方式输入，只能用getchar、fgets或者getline。
另外我在用fgets读入的时候产生了一个衍生陷阱：fgets读入S的长度定义应当大于101，实测发现101会WA。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 105;int n;
char s[N];
int dp[N][N];bool match(char a, char b)
{return a == '(' && b == ')' || a == '[' && b == ']';
}void print(int i, int j)
{if (i > j) return ;if (i == j) {if (s[i] == '(' || s[i] == ')') printf("()");else printf("[]");return ;}int ans = dp[i][j];if (match(s[i], s[j]) && ans == dp[i+1][j-1]) {printf("%c", s[i]); print(i+1, j-1); printf("%c", s[j]);return ;}for (int k = i; k < j; k++) {if (ans == dp[i][k] + dp[k+1][j]) {print(i, k); print(k+1, j);return ;}}
}int main(void)
{int kase;scanf("%d", &kase);getchar();while (kase--) {getchar();fgets(s, N, stdin);n = strlen(s)-1;memset(dp, -1, sizeof(dp));for (int j = 0; j < n; j++) {dp[j][j] = 1;dp[j+1][j] = 0;}for (int i = n-2; i >= 0; i--) {for (int j = i+1; j < n; j++) {dp[i][j] = n;if (match(s[i], s[j])) dp[i][j] = min(dp[i][j], dp[i+1][j-1]);for (int k = i; k < j; k++)dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);}}print(0, n-1);printf("\n");if (kase) printf("\n");}return 0;
}

例9-11 UVA 1331 最大面积最小的三角剖分（未尝试）

题意

思路

代码

例9-12 UVA 12186 工人的请愿书

题意
某公司里有一个老板和n（n≤105）个员工组成树状结构，除了老板之外每个员工都有唯一的直属上司。老板的编号为0，员工编号为1～n。工人们（即没有直接下属的员工）打算签署一项请愿书递给老板，但是不能跨级递，只能递给直属上司。当一个中级员工（不是工人的员工）的直属下属中不小于T%的人签字时，他也会签字并且递给他的直属上司。问：要让公司老板收到请愿书，至少需要多少个工人签字？

思路
设d(u)表示让u给上级发信最少需要多少个工人。假设u有k个子结点，则至少需要c=(kT-1)/100+1个直接下属发信才行。把所有子结点的d值从小到大排序，前c个加起来即可。最终答案是d(0)。因为要排序，算法的时间复杂度为O(nlogn)。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;const int N = 100005;int n, t;
vector<int> sons[N];int dp(int k)
{if (sons[k].empty()) return 1;vector<int>& s = sons[k];int len = s.size(), m = len*t;if (m % 100) m = m/100+1;else m = m/100;vector<int> d;for (int i = 0; i < len; i++)d.push_back(dp(s[i]));if (m < len) sort(d.begin(), d.end());int res = 0;for (int i = 0; i < m; i++)res += d[i];//printf("k=%d, len=%d, m=%d, res=%d\n", k, len, m, res);return res;
}int main()
{while (scanf("%d%d", &n, &t), n || t) {for (int i = 0; i <= n; i++)sons[i].clear();int father;for (int i = 1; i <= n; i++) {scanf("%d", &father);sons[father].push_back(i);}printf("%d\n", dp(0));}return 0;
}

例9-13 UVA 1220 Hali-Bula的晚会

题意
公司里有n（n≤200）个人形成一个树状结构，即除了老板之外每个员工都有唯一的直属上司。要求选尽量多的人，但不能同时选择一个人和他的直属上司。问：最多能选多少人，以及在人数最多的前提下方案是否唯一。

思路
本题几乎就是树的最大独立集问题，不过多了一个要求：判断唯一性。设：

d(u,0)和f(u,0)表示以u为根的子树中，不选u点能得到的最大人数以及方案唯一性（f(u,0)=1表示唯一，0表示不唯一）。
d(u,1)和f(u,1)表示以u为根的子树中，选u点能得到的最大人数以及方案唯一性。相应地，状态转移方程也有两套。
d(u,1)的计算：因为选了u，所以u的子结点都不能选，因此d(u,1) = sum{d(v,0) | v是u的子结点}。当且仅当所有f(v,0)=1时f(u,1)才是1。
d(u,0)的计算：因为u没有选，所以每个子结点v可选可不选，即d(u,0) = sum{ max(d(v,0) ,d(v,1)) }。什么情况下方案是唯一的呢？首先，如果某个d(v,0)和d(v,1)相等，则不唯一；其次，如果max取到的那个值对应的f=0，方案也不唯一（如d(v,0) > d(v,1)且f(v,0)=0，则f(u,0)=0）。

我的做法与书中思路大体一直，细节略有不同，也可供参考。

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;const int N = 202;map<string, int> ids;
vector<string> names;int n;
int fth[N];
vector<int> sons[N];
int d[N][2];
bool sg[N][2];void init()
{memset(fth, 0, sizeof(fth));for (int i = 0; i < n; i++)sons[i].clear();ids.clear();names.clear();for (int i = 0; i < n; i++) {d[i][0] = 0; d[i][1] = 1;sg[i][0] = sg[i][1] = 1;}
}int ID(string s)
{if (ids.count(s)) return ids[s];names.push_back(s);return ids[s] = names.size()-1;
}void dp(int k)
{for (int i = 0; i < sons[k].size(); i++)dp(sons[k][i]);if (d[k][1] > d[k][0]) sg[k][0] = sg[k][1];else if (d[k][0] == d[k][1]) sg[k][0] = 0;d[k][0] = max(d[k][0], d[k][1]);//printf("k=%d, size=%d, d[k][0]=%d, sg[k][0]=%d\n", k, sons[k].size(), d[k][0], sg[k][0]);if (k) {int f = fth[k];d[f][0] += d[k][0];sg[f][0] &= sg[k][0];if (f) {int ff = fth[f];d[ff][1] += d[k][0];sg[ff][1] &= sg[k][0];}}
}int main()
{string s;while (scanf("%d", &n), n) {init();cin >> s;ID(s);string f[N];for (int i = 1; i < n; i++) {cin >> s >> f[i];ID(s);}for (int i = 1; i < n; i++) {fth[i] = ID(f[i]);sons[fth[i]].push_back(i);}dp(0);printf("%d %s\n", d[0][0], sg[0][0] ? "Yes" : "No");}return 0;
}

例9-14 UVA 1218 完美的服务

题意
有n（n≤10000）台机器形成树状结构。要求在其中一些机器上安装服务器，使得每台不是服务器的计算机恰好和一台服务器计算机相邻。求服务器的最少数量。如图9-15所示，图9-15（a）是非法的，因为4同时和两台服务器相邻，而6不与任何一台服务器相邻。而图9-15（b）是合法的。

思路
有了前面的经验，这次仍然按照每个结点的情况进行分类。

d(u,0)：u是服务器，则每个子结点可以是服务器也可以不是。
d(u,1)：u不是服务器，但u的父亲是服务器，这意味着u的所有子结点都不是服务器。
d(u,2)：u和u的父亲都不是服务器。这意味着u恰好有一个儿子是服务器。

状态转移比前面复杂一些，但也不困难。首先可以写出：

d(u,0) = sum{min(d(v,0), d(v,1))} + 1
d(u,1) = sum(d(v,2))

而d(u,2)稍微复杂一点，需要枚举当服务器的子结点编号v，然后把其他所有子结点v’的d(v’,2)加起来，再和d(v,0)相加。不过如果这样做，每次枚举v都需要O(k)时间（其中k是u的子结点数目），而v本身要枚举k次，因此计算d(u,2)需要花O(k^2)时间。刚才的做法有很多重复计算，其实可以利用已经算出的d(u,1)写出一个新的状态转移方程：

d(u,2) = min(d(u,1) – d(v,2) + d(v,0))

这样一来，计算d(u,2)的时间复杂度变为了O(k)。因为每个结点只有在计算父亲时被用了3次，总时间复杂度为O(n)。

另外需要注意的是，最终的结果应该是min(d[1][0], d[1][2])，其中不包括d[1][1]（因为1作为根节点，没有父亲）。

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;const int N = 10002;int n;
vector<int> G[N], list;
int p[N], d[N][3];void init()
{for (int i = 1; i <= n; i++)G[i].clear();list.clear();for (int i = 1; i <= n; i++) {p[i] = 0;d[i][0] = 1; d[i][1] = d[i][2] = 0;}
}void dfs(int k, int fa)
{p[k] = fa;for (int i = 0; i < G[k].size(); i++) {int u = G[k][i];if (u != fa) dfs(u, k);}list.push_back(k);
}int main()
{string s;while (scanf("%d", &n), n) {init();int a, b;for (int i = 1; i < n; i++) {scanf("%d%d", &a, &b);G[a].push_back(b);G[b].push_back(a);}dfs(1, -1);for (int i = 0; i < list.size(); i++) {int k = list[i];for (int r = 0; r < G[k].size(); r++) {int u = G[k][r];if (u != p[k]) {d[k][0] += min(d[u][0], d[u][1]);d[k][1] += d[u][2];}}d[k][2] = n;for (int r = 0; r < G[k].size(); r++) {int u = G[k][r];if (u != p[k])d[k][2] = min(d[k][2], d[k][1]-d[u][2]+d[u][0]);}}printf("%d\n", min(d[1][0], d[1][2]));scanf("%d", &n);if (n == -1) break;}return 0;
}