最长上升子序列
最长上升子序列（longest increasing subsequence） ，是动态规划中一个经典的问题。
定义如下：对于一个序列$A_1 \cdots A_i \cdots A_n$，子序列$A_{b_1} \cdots A_{b_i} \cdots A_{b_len}$满足：$B_i \lt B_{i+1} \ (foreach \ 1 \le i \lt len)$，$A_{B_i} \lt A_{B_{i+1}} \ (foreach \ 1 \le i \lt len)$，且$len$最大，则子序列$A_{b_1} \cdots A_{b_i} \cdots A_{b_len}$是序列$A_1 \cdots A_i \cdots A_n$的最长上升子序列。
第一种DP，$f[i]$代表$i$作为子序列的最后一个元素的最长上升子序列长度。$f[i]$转移的话可以枚举它前面的那个元素，所以有以下转移：$f[i] = max{f[j] + 1} \ (1 \le j \lt i \ \& \& \ a[i] \lt a[j])$。这个DP是状态一维，转移一维的，所以时间复杂度为$O(n^2)$。
对于这种DP，还可以用数据结构优化，平衡树或者离散+线段树（或树状数组），优化后的时间复杂度都是$O(nlog_{2}n)$。
关于方案的话，只要记录$pre[i]$为$i$从前面转移过来的位置。第二种DP，$c[i]$代表上升子序列长度为$i$时，最后一个元素的最小值，$len$为最长上升子序列长度。考虑一个个把原序列的元素加入，对于当前的第$i$个元素，在之前的状态下找到一个最大的$j$，满足$c[j - 1] < a[i] \ (1 \le j \ \& \& \ j \le len + 1)$，以它为最后一个元素的最长上升子序列就是以第$j$个元素为最后一个元素的最长上升子序列加上当前的第$i$个元素。因为随着上升子序列的变长，它的最后一个元素的值会越来越大，所以$c$数组是单调的，所以$j = lower \underline{} bound(c + 1, c + len + 1, a[i])$。
关于方案的话，$c[j - 1]$在原序列的位置就是$pre[i]$。
最长下降子序列，最长不上升子序列，最长下降子序列也类似可求。
以下是最长上升子序列。
$a$数组是原序列，$n$是序列长度，$c$是辅助数组。
int LIS(int *a, int n, int *c) {
int len = 0;
for (int i = 1; i <= n; ++i) {
int j = lower_bound(c + 1, c + len + 1, a[i]) - c;
c[j] = a[i];
if (len < j) len = j;
}
return len;
}
合唱队形
题目描述
$n$位同学站成一排，音乐老师要请其中的$(n - k)$位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设$k$位同学从左到右依次编号为$1, 2, \cdots , k$，他们的身高分别为$t_1, t_2, \cdots , t_k$， 则他们的身高满足$t_1 \lt \cdots \lt t_i \gt t_{i+1} \gt \cdots \gt t_k \ (1 \le i \le k)$。
你的任务是，已知所有$n$位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入格式
输入第一行是一个整数$n$，表示同学的总数。第一行有$n$个整数，用空格分隔，第i个整数$t_i \ (130 \le t_i \le 230)$是第$i$位同学的身高。
输出格式
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
输入样例
8
186 186 150 200 160 130 197 220
输出样例
4
说明
对于50％的数据，保证有$n \le 20$；
对于全部的数据，保证有$n \le 100$。
题解
为了让更少的同学出列，应计算出最长的合唱队形。
分别从前往后和从后往前做两遍最长上升子序列，算出每个同学作为最后一个元素的最长上升子序列$f[i]$和第一个元素的最长下降子序列$g[i]$，那么第$i$个同学作为中间最高的最长合唱队形的长度为$f[i] + g[i] - 1$。
因为本题数据范围很小，上述所以方法都可以过。
时间复杂度为$n^2$或$O(nlog_{2}n)$。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 110;
int n;
int t[N], f[N], g[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &t[i]);
for (int i = 1; i <= n; ++i) {
f[i] = 1;
for (int j = 1; j < i; ++j)
if (t[j] < t[i] && f[j] >= f[i]) f[i] = f[j] + 1;
}
for (int i = n; i >= 1; --i) {
g[i] = 1;
for (int j = n; j > i; --j)
if (t[i] > t[j] && g[j] >= g[i]) g[i] = g[j] + 1;
}
int res = 0;
for (int i = 1; i <= n; ++i)
if (res < f[i] + g[i] - 1) res = f[i] + g[i] - 1;
printf("%d\n", n - res);
return 0;
}
导弹拦截
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于$50000$的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，若干个整数（个数少于$100000$）。
输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入样例
389 207 155 300 299 170 158 65
输出样例
6
2
说明
第一问直接做最长不下降子序列。
对于第二问，有以下贪心：对于当前的导弹，若目前所有的导弹拦截系统的高度都小于其高度，那么要新开一个导弹拦截系统，否则找到一个高度不小于它且高度最小的导弹拦截系统来拦截它。这样直接做是$O(n^2)$的，但是注意到当前所以导弹拦截系统的高度都是不下降的，每次找到一个第一个不小于它的导弹拦截系统来拦截它，这与我们的第二种DP是一样的，所以其实它就是原序列的最长上升子序列的长度。
时间复杂度为$O(nlog_{2}n)$。
标程
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N], c[N];
int main() {
for (n = 0; scanf("%d", &a[n + 1]) == 1; ++n);
int len = 0;
for (int i = n; i; --i) {
int j = upper_bound(c + 1, c + len + 1, a[i]) - c;
c[j] = a[i];
if (len < j) len = j;
}
printf("%d\n", len);
len = 0;
for (int i = 1; i <= n; ++i) {
int j = lower_bound(c + 1, c + len + 1, a[i]) - c;
c[j] = a[i];
if (len < j) len = j;
}
printf("%d\n", len);
return 0;
}
Beautiful People
Description
The most prestigious sports club in one city has exactly N members. Each of its members is strong and beautiful. More precisely, i-th member of this club (members being numbered by the time they entered the club) has strength $S_i$ and beauty $B_i$. Since this is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if $S_i \le S_j$ and $B_i \ge B_j$ or if $S_i \ge Sj$ and $B_i \le B_j$ (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn’t even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).
To celebrate a new 2003 year, the administration of the club is planning to organize a party. However they are afraid that if two people who hate each other would simultaneouly attend the party, after a drink or two they would start a fight. So no two people who hate each other should be invited. On the other hand, to keep the club prestige at the apropriate level, administration wants to invite as many people as possible.
Being the only one among administration who is not afraid of touching a computer, you are to write a program which would find out whom to invite to the party.
Input
The first line of the input file contains integer N — the number of members of the club. ($2 \le N \le 100000$). Next N lines contain two numbers each — Si and Bi respectively ($1 \le S_i, B_i \le 10^9$).
Output
On the first line of the output file print the maximum number of the people that can be invited to the party. On the second line output N integers — numbers of members to be invited in arbitrary order. If several solutions exist, output any one.
Example
people.in
4
1 1
1 2
2 1
2 2
people.out
2
1 4
Solution
一个俱乐部有$n$个成员，每个成员有力量值$S_i$和美丽值$B_i$，成员$i$与成员$j$互相讨厌当且仅当$(S_i \le S_j \ \& \& \ B_i \ge B_j) \ | | \ (S_i \ge Sj \ \& \& \ B_i \le B_j)$。现在该俱乐部要组织一个聚会，问你最多邀请多少人，满足他们都不互相讨厌，输出最多人数及方案（任意一种）。
分析发现，对于合法安排方案的两个成员$i,j$，$S_i \neq S_j \ \& \& \ B_i \neq B_j \ \& \& \ sgn(S_i - S_j) = sgn(B_i - B_j)$。
那么这就是一个二维的最长上升子序列问题，先对第一维排序，再对第二位做最长上升子序列。因为最后的子序列的第一维不能相同，所以我们排序时先对第一维从小到大排序，第一维相同的按第二维从大到小排序，这样保证了第一维相同的第二维小的不会更新第二维大的，保证了算法的正确性。
这题还要输路径，与就是普通的输路径方法。
时间复杂度为$O(nlog_{2}n)$。
Standrad
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
inline void FO() {
freopen("people.in", "r", stdin);
freopen("people.out", "w", stdout);
return;
}
const int N = 100010, INF = 0x7fffffff;
int n, len;
int pre[N], from[N], c[N];
struct Node {
int s, b, idx;
bool operator < (const Node &a) const {
return (s != a.s) ? (s < a.s) : (b > a.b);
}
} a[N];
int main() {
FO();
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i].s, &a[i].b);
a[i].idx = i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) {
int k = lower_bound(c + 1, c + len + 1, a[i].b) - c;
c[k] = a[i].b;
from[k] = i;
pre[i] = from[k - 1];
if (len < k) len = k;
}
printf("%d\n", len);
for (int i = from[len]; i; i = pre[i])
printf("%d ", a[i].idx);
putchar('\n');
return 0;
}
Longest Increasing Subsequence
Description
Note that the memory limit in this problem is less than usual.
Let’s consider an array consisting of positive integers, some positions of which contain gaps.
We have a collection of numbers that can be used to fill the gaps. Each number from the given collection can be used at most once.
Your task is to determine such way of filling gaps that the longest increasing subsequence in the formed array has a maximum size.
Input
The first line contains a single integer $n$ — the length of the array ($1 \le n \le 10^5$).
The second line contains $n$ space-separated integers — the elements of the sequence. A gap is marked as “-1”. The elements that are not gaps are positive integers not exceeding $10^9$. It is guaranteed that the sequence contains $0 \le k \le 1000$ gaps.
The third line contains a single positive integer $m$ — the number of elements to fill the gaps ($k \le m \le 10^5$).
The fourth line contains $m$ positive integers — the numbers to fill gaps. Each number is a positive integer not exceeding $10^9$. Some numbers may be equal.
Output
Print $n$ space-separated numbers in a single line — the resulting sequence. If there are multiple possible answers, print any of them.
Examples
input
3
1 2 3
1
10
output
1 2 3
input
3
1 -1 3
3
1 2 3
output
1 2 3
input
2
-1 2
2
2 4
output
2 2
input
3
-1 -1 -1
5
1 1 1 1 2
output
1 1 2
input
4
-1 -1 -1 2
4
1 1 2 2
output
1 2 1 2
Solution
给你一个长度为$n$的序列，序列中有$k$个位置是空缺的，你现在有$m$个数，你可以把它们填入空缺的位置，每个数只能用一次，最大化最后序列的最长上升子序列的长度，输出最后序列。
因为一个最长上升子序列中不会有重复的数，所以可以假设可填的数可以用多次，就先把可填的数排序。
用第二种DP。1. 对于原来就有的位置，直接$lower \underline{} bound$求。2. 对于空缺的位置，可以一次$O(n)$求出所有可填的数的$lower \underline{} bound$。
安排最长上升子序列的空缺位置后，随意安排剩下的空缺的位置。
时间复杂度为$O(nlog_{2}n + mlog_{2}m + k \times m)$。
Standrad
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 0x7fffffff;
int n, m, len;
int a[N], b[N], c[N], pre[N], from[N], temp[N];
bool v[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 1; i <= m; ++i)
scanf("%d", &b[i]);
sort(b + 1, b + m + 1);
for (int i = 1; i <= n; ++i)
if (~a[i]) {
int j = lower_bound(c + 1, c + len + 1, a[i]) - c;
pre[i] = from[j - 1];
from[j] = i;
c[j] = a[i];
if (len < j) len = j;
} else {
int j = 1;
for (int k = 1; k <= m; ++k) {
while (j <= len && c[j] < b[k]) ++j;
temp[k] = j;
}
if (len < j) len = j;
for (int k = m; k; --k) {
c[temp[k]] = b[k];
from[temp[k]] = from[temp[k] - 1];
}
}
int cnt = 0;
for (int i = from[len]; i; i = pre[i])
temp[++cnt] = i;
temp[0] = n + 1;
temp[cnt + 1] = 0;
a[n + 1] = INF;
for (int i = cnt + 1; i; --i) {
int last = a[temp[i]];
for (int j = temp[i] + 1; j < temp[i - 1]; ++j)
if (!~a[j]) {
int k = upper_bound(b + 1, b + m + 1, last) - b;
if (k > m || b[k] >= a[temp[i - 1]]) break;
last = a[j] = b[k];
v[k] = 1;
}
}
for (int i = 1, j = 1; i <= n; ++i)
if (!~a[i]) {
while (j < m && v[j]) ++j;
a[i] = b[j];
v[j] = 1;
}
//cerr << len << endl;
for (int i = 1; i <= n; ++i)
printf("%d ", a[i]);
putchar('\n');
return 0;
}