经典题目杂选1

现在连简单题都不会了……GG。

I 正整数拆分

对于一个数 $N (1 \leqslant N \leqslant 120)$ ，要求求出将其拆分为若干个正整数的方案数。

记得以前这题得用搜索+回溯

想必这里搜索是GG的。于是可以dp。我们用 $dp[i][j]$ 来表示将数 $i$ 划分成若干个均不大于 $j$ 的数的方案数，那么可以得到转移方程：

预处理到最大数据范围就可以了。

II K路归并

给出 $m$ 个数列，每个数列有 $n$ 个数，现要从每个数列中挑选一个数并求和，共有 $n^m$ 种情况。需要输出这些情况中前 $n$ 小的值。

为什么这道题可以转化为K路归并呢？我们先考虑只有 $2$ 个数列的情况：

这两个长为 $n$ 的数列共可以组成 $n^2$ 个和值。假设这两个数列为 $A$ 和 $B$ ，并且已经排好了序，我们就可以将这 $n^2$ 个值排列成下面这样的 $n$ 个数列：

可以发现这 $n$ 个数列也都是有序的。那么既然问题是求这些数中的前 $n$ 个数，那就只要将这些有序表归并求得前 $n$ 项就可以了。

那么扩展到有 $m$ 个数列的情况，我们只要两两合并即可。

至于 $K$ 路归并的方法，和二路归并相似，每次取 $m$ 个队首的最值，加入答案序列即可。维护一个堆可以每次在 $O(\log m)$ 的时间内求得队首最值，因为堆里最多只可能有 $m$ 个元素。

III 最长上升子序列

有 $n$ 个人，每个人有一个美丽值 $A_i$ 和力量值 $B_i$ 。两个人 $i$ 和 $j$ 是互相讨厌的当且仅当 $A_i \leqslant A_j$ 且 $B_i \geqslant B_j$ 。现在需要邀请尽可能多的人参加一个聚会，使得参加的人中没有任何两个人是互相讨厌的。输出最多人数以及选取方案。

分析题意后可以发现，对于两个人 $i$ 和 $j$ ，当 $A_i \leqslant A_j$ 时，只有 $B_i > B_j$ 时这两个人才能被邀请。所以我们对所有人按其美丽值从小到大排序，当美丽值相同时，按力量值从大到小排序。然后对排序后所有人的力量值求最长上升子序列（严格递增）即可。这样选取出的人均满足上面的条件。为什么当美丽值相同时，力量值要从大到小排序呢？仔细体会一下，如果从此时力量值小到大排序的话，求最长上升子序列时，会把这些人全部取走，但是这样是不满足条件的，只有从大到小排序才能使得对于在美丽值相同的人中最多只选取一个。

由于数据范围和时间限制，这道题不能使用 $O(n^2)$ 的算法求解，需要 $O(n \log n)$ 的时间复杂度。这里我们维护一个数组 $f$ ，其中 $f[i]$ 表示长度为 $i$ 的上升子序列的末尾元素值。然后我们扫一遍原数组，对于当前一个新数 $x$ ，设当前最长上升子序列长度为 $len$ ，如果 $x > f[len]$ ，那么将 $f[len+1]$ 赋值为 $x$ ，同时把 $len$ 值加一，更新答案；如果 $x \leq f[len]$ ， 那么在 $f[1]$ ~ $f[len]$ 中找到一个 $x$ 所能替换的位置，也就是找到第一个大于等于 $x$ 的值的位置，将其修改成 $x$ 即可。如何寻找这个位置呢？由于 $f$ 数组是有序的，所以二分是个很好的选择。这样复杂度就降到了 $O(n \log n)$

至于输出解的问题，只要对每个数记录一下它的前驱节点，最后递归输出就可以了。

	f[0]=0;
	f[1]=a[1];
	len=1;
	for(int i=2;i<=n;++i) {
		if(a[i]>f[len]) {
			pre[i]=f[len];
			f[++len]=a[i];
		} else {
			int tmp=lower_bound(f+1,f+1+len,a[i])-f;
			pre[i]=idx[f[tmp-1]];
			f[tmp]=a[i];
		}
	}