这一周主要在看 DP 的题目，嘛，都是一些我觉得很好但是我写不出来的题。本周的话做的都是 HDU 的题，虽然看了一下 Codeforces 上的一两道这样子。感觉收获还是蛮多的。
偶然学到的黑科技
在开始正式的记题之前，想先记一下这周做题和看题解的时候新学到的东西。
STL 的 unique()
STL 中提供了一个很方便的去重函数 unique(), 其功能是去除相邻的重复元素（只保留一个），所以使用前需要对数组进行排序。用 unique 之后对于有序数组就不用手动循环去重了。
STL lower_bound() 和 upper_bound()
lower_bound(arr, arr + n, val) 返回在有序数组 arr 的 [0, n) 区间中的第一个不小于 val 的值的地址。
相反的，upper_bound(arr, arr + n, val) 则返回第一个不小于 val 的值的地址。
所以，我们可以利用这个好东西：
四行写出最长上升子序列 (LIS) 的 O(nlogn) 解法
LIS 的话，传统的写法是 O(n^2) 的，用二分优化过后可以降到 O(nlogn). 至于具体的原理我就不想详细在这里记录了，不然文章又要很长。
设 arr[] 为要求 LIS 的数列，lis[] 为保存 LIS 的数组。那么我们可以通过下面的代码来求 LIS：
fill(lis, lis + n, INF);
for (int i = 0; i < n; i++)
*lower_bound(lis, lis + n, arr[i]) = arr[i];
int len = lower_bound(lis, lis + n, INF) - lis; // LIS 的长度
简单快捷。
4⁄200, HDU1024, Max Sum Plus Plus
题意 & 扯淡
DP, 最大 m 子段和。没错题目很眼熟，是 P1003 的升级版，原题是最大连续子段和，这题是 n 子段和。是个挺不错的题目，之所以这么说是因为我不会它的时间和空间限制挺严格的，尤其是空间限制是 32M….emmm….
题意还是给你一个很长的数列 a1….an，然后让你找出它的 m 个子序列使得这些子序列的总和最大，输出这个总和。1 <= n <= 1e6, m 的范围未知。注意就是求出的区间不能相交。
和上一题比一个比较人道的地方就是这一题不用输出位置了。但是反而比上一题更难了。看到 32M 的内存限制，反正你想到的不是正解的解法表示状态都需要二维，肯定就 GG 了。这道题的正解是用滚动数组优化，非常巧妙，以至于我到现在还不是很理解。
说的不太清楚，如果没明白的可以看看别人写的。直接从 notepad 复制过来的，不想理通顺了，凑合着看吧。
开始正文
虽然这道题的数据范围感人，n <= 1e6, m 未知，内存 32M. 基本上告诉我们的信息就是二维的数组都开不下了，那么肯定要做一些黑科技的优化。但是这道题直接看正解是很难理解的，包括我现在看了正解还是有些地方不太明白，下面的解析是我按自己的理解 YY 的，可能有些地方并不一定对。
在正解之前，我们先来理解不做没优化的情况。如果抛开限制不谈，那么这道题的状态还是很好表示的。用 dp[i][j] 表示当子区间个数为 i，选取第 j 个数的时候的最大值。
对于 dp[i][j] 的值有两种决策：
1.将第 j 个数合并到第 i 个区间，区间个数不变，最大和为 dp[i][j-1]+a[j]. 2.将第 j 个数单独划一个区间，此时区间个数由 i-1 变为 i，最大和为当区间长度为 i-1 的时候能取到的最大值 (也就是 dp[i-1][k]) 加上 a[j].
我们可以得到这样的状态转移方程：
dp[i][j] = max(dp[i][j-1] + a[j], dp[i-1][k] + a[j]), 其中 k∈[i-1, j-1]
也即
dp[i-1][k] = max(dp[i-1][i-1], dp[i-1][i], ....., dp[i-1][j-1]).
意思是，dp[i][j] 的取值只和 dp[i][j-1] 和 dp[i-1][k] 有关。由于 i = 1 => m，那么我们事实上可以将数组降成两个一维的，也就是运用滚动数组来解这道题目：
设 d[j] 表示第 j 个数一定取的时候的最大值(dp[i][j])，premax[j] 表示 max(dp[i][i], …, dp[i][j])。那么原方程就可以化为 dp[j] = max(dp[j-1] + a[j], premax[j-1] + a[j]);
我们首先枚举区间的数量，用 curmax 表示当区间个数为 i 的时候能取得的最大值是多少，初始值为 -INF。
接着，我们枚举剩余的所有没有划分区间的数，每次枚举首先计算 dp[j]，然后再将 premax[j-1] 设为 curmax，然后更新 curmax 的值为 max(curmax, dp[j]). curmax 在这里的作用就相当于表示了 max(dp[i-1][i-1], …, dp[i-1][j-1])，我们可以利用滚动数组边 DP 边计算 curmax，然后把 curmax 更新给 premax 来保存. 全部计算完之后最后的结果就是最后一次更新后的 curmax 值了。
核心的伪代码如下：
initialize curmax
for (i = 1 => m)
let curmax = -infinity
for (j = i => n)
calculate dp[j] = max(dp[j-1] + a[j], premax[j-1] + a[j])
update premax[j-1] = curmax
update curmax = max(dp[j], curmax)
print curmax
代码
/**
* HDU1024 DP 最大连续 m 区间和
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const int INF = 1e9 + 7;
int n, m;
int a[MAXN];
int dp[MAXN];
int premax[MAXN];
int main()
{
while (scanf("%d%d", &m, &n) != EOF)
{
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 0; i <= n; i++)
{
dp[i] = 0;
premax[i] = 0;
}
// start solution
int curmax;
for (int i = 1; i <= m; i++)
{
curmax = -INF;
for (int j = i; j <= n; j++)
{
dp[j] = max(dp[j-1] + a[j], premax[j-1] + a[j]);
premax[j-1] = curmax;
curmax = max(curmax, dp[j]);
}
}
printf("%d\n", curmax);
}
return 0;
}
5⁄200, HDU1028, Ignatius and the Princess III
题意 & 扯淡
依旧是 DP，虽然传闻有母函数的做法，但是本蒟蒻不知道也不会写什么母函数。题意大概就是给你一个整数 n，然后你看看这个整数 n 有多少种划分方法，例如说:
4 = 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 +1
所以 4 有 5 种划分方法。
正文
题意就是整数划分嘛，给定一个整数 n，求 n 有多少种分法，然后不能重复。
一开始都没想到是 DP 题……为什么可以用 DP 呢，一定是因为有重复计算的步骤啦。比如说我们要划分整数 4，把 4 划分到 3+1 的时候，显然 3 还能再往下划分，那么我们就可以直接利用之前已经计算过的结果了。
网上现成的 DP 题解大概有两种说法，但是状态转移方程是一样的。这个方程挺好写，但是不好想。
第一种解法是设 dp[i][j] 为将整数 i 划分为最多 j 个数的和的时候最多的方案数量。我觉得这种方案不太好理解，尤其是分类讨论的时候。所以以下分析以第二种解法为基础：设 dp[i][j] 为将整数 i 划分为不超过 j 的数的和的时候最多的方案数量。
1) 显然，当 i = 1 的时候，区间长度只能是 1，那么只有一种方法，也即 dp[1][1] = 1.
2) 当 i < j 的时候，由于不可能出现“目标数是 i，但是 j(j > i) 是 i 的一个加数”的情况，所以我们让 dp[i][j] = dp[i][i].
3) 当 i = j 的时候，dp[i][j] = dp[i][j-1] + 1
(1) 用不超过 j 的整数划分的时候，我们考虑是否要分出 j 这个数，如果要分的话由于 n = m 那么只有一种方案，就是 m 本身（对应状态转移方程中的 1），如果不分，那么就是继承 dp[i][j-1] 的结果，即把 i 分成最大加数不超过 j-1 的多少份。
(2) 如果我们用第一种解法来理解这个式子，那么 dp[i][j] = 将 i 分成 j-1 段的方案数最大值 + 将 i 分成 j 段的方案数，由于 i = j，那么将 i 分成 j 段只有一种方案，就是有 j 个 1 的情况。
4) 当 i > j 的时候，也是最不好理解的一个部分。这个时候我们可以发现一个包含 i 个数的集合 U={1, 2, 3, …, i} 可以被 j 划分为两部分：一个是 A={j}，一个是 CU(A). 那么这个时候我们可以考虑是否要分出 j 这个数：如果要分出 j，那么我们只要计算剩下来的数的分离方案数，就是 dp[i-j][j]；如果不分，那么答案还是把 i 分成不超过 j-1 的结果，也就是 dp[i][j-1]. 将两种方案相加，我们得到了 dp[i][j] = dp[i-j][j] + dp[i][j-1];
“这样我们就完美地解决了这个问题。”
代码
#include <bits/stdc++.h>
const int MAXN = 120 + 5;
int n;
int dp[MAXN][MAXN];
int main()
{
while (scanf("%d", &n) != EOF)
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i < j)
{
dp[i][j] = dp[i][i];
}
if (i == j)
{
dp[i][j] = dp[i][j-1] + 1;
}
if (i > j)
{
dp[i][j] = dp[i][j-1] + dp[i-j][j];
}
}
}
printf("%d\n", dp[n][n]);
}
return 0;
}
6⁄200, HDU1025 Constructing Roads In JGShining’s Kingdom
还是 DP。懒得翻题意了，自己戳原链接看好了QAQ：http://acm.hdu.edu.cn/showproblem.php?pid=1025
也就是在上文提到的最长上升子序列了，但是这一题的话用 O(n^2) 的解法是会 T 的。有两组数嘛，首先对一组排序（当然要保持和另外一组的对应关系），然后对另一组数做 LIS 就可以了。为什么是 LIS 自己画个图就知道了。
甚至可以，不用排序：在输入的时候只保存一组数据，而把另一组数作为数组的 key 即可，因为两组数是一一对应的，没有一对多的情况。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5 * 1e5 + 10;
const int INF = 1e9 + 10;
int n;
int ans = 0, kases = 0;
int maps[MAXN];
int dp[MAXN];
int LIS[MAXN];
int main()
{
while (scanf("%d", &n) == 1)
{
kases++;
// read data
for (int i = 1; i <= n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
maps[x] = y;
}
// initialize
for (int i = 0; i <= n; i++)
{
dp[i] = 0;
LIS[i] = INF;
}
dp[0] = 0;
// LIS
for (int i = 1; i <= n; i++)
{
*lower_bound(LIS + 1, LIS + 1 + n, maps[i]) = maps[i];
}
ans = lower_bound(LIS + 1, LIS + 1 + n, INF) - LIS - 1;
printf("Case %d:\n", kases);
printf("My king, at most %d ", ans);
if (ans == 1)
{
printf("road can be built.\n");
}
else
{
printf("roads can be built.\n");
}
printf("\n");
}
return 0;
}
以下是自己写的时候顺手 YY 的注释:
/** * 附 nlogn 版的 LIS 写法： * 设 LIS[MAXN] 为此数列的取得 LIS 最大值时的 LIS 一种可能的情况； * 首先把 LIS 数组设为 INF：fill(LIS + 1， LIS + 1 + n, INF) ; * 然后遍历数列，利用 lower_bound 函数二分查找到 LIS 中第一个不大于 a[i] 的值的位置 pos， * 然后把 LIS[pos] 设为 a[i]. 也即 *lower_bound(LIS + 1, LIS + 1 , n, a[i]) = a[i]; * 最后统计 LIS 中不是 INF 的值的个数就可以了，即 ans = lower_bound(LIS + 1, LIS + 1 + n, INF); */
6.1, HDU1029, Ignatius and the Princess IV
之所以是 6.1 是因为这题实在是太。水。了。不是一般的水。要不是某个题目分类的帖子里说这题是 DP，我才不会做呢（
/**
* HDU1029 水题，谁说是 DP 的给我出来我保证打不死你
* 明明是这么简单的计数题！！
*/
#include <bits/stdc++.h>
const int MAXN = 1e6 + 5;
int data[MAXN];
int main()
{
int n, flag;
while (scanf("%d", &n) != EOF)
{
bool state = true;
flag = (n + 1) / 2;
memset(data, 0, sizeof(data));
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
data[x]++;
if (data[x] >= flag && state)
{
printf("%d\n", x);
state = false;
}
}
}
return 0;
}
6.5⁄200, HDU1232, 畅通工程
畅通工程系列的第一题，这是一道裸的并查集 OvO. 只要理解并查集的都会写啦。题目有个“温馨提示”，但是并不影响我们做题，管他什么多条道路连接的输入合不合法呢。
#include <bits/stdc++.h>
const int MAXN = 1e3 + 10;
int p[MAXN];
int n, m;
int cnt = 0;
void init()
{
cnt = 0;
for (int i = 0; i < MAXN; i++)
{
p[i] = i;
}
}
int find(int x)
{
return x == p[x] ? x : p[x] = find(p[x]);
}
void unions(int x, int y)
{
int px = find(x),
py = find(y);
if (px == py)
{
return;
}
else
{
p[px] = py;
cnt++;
}
}
int main()
{
while (scanf("%d", &n) != EOF && n != 0)
{
init();
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
unions(x, y);
}
printf("%d\n", (n - 1 - cnt));
}
return 0;
}
剩下的是一些旧题重做的，然后就不贴上来了。