序列动态规划
一. 关于最长上升/下降/不上升/不下降子序列
题目大意 ：给定一个序列，求当前序列中最长上升/下降/不上升/不下降子序列（序列可以不连续）
注 ：以下算法皆由最长上升子序列展示
1. Ο(n2)
思路 ：f[i]表示以q[i]结尾的最长上升子序列的长度，初始值为1。每次循环1 ~ n，再循环1 ~ i - 1，如果q[i] > q[j]（要上升啊），就f[i] = max(f[i], f[j] + 1)（这个 + 1是因为还要加上q[i]啊）
code ：
1 #include2 using namespace std; 3 int n, q[100001], f[100001], maxl; 4 inline void memset(int a[], int b, int l)//手写memset 5 { 6 for(register int i = 1; i <= l; ++i) 7 { 8 a[i] = b; 9 }10 return;11 }12 signed main()13 {14 scanf("%d", &n);15 for(register int i = 1; i <= n; ++i)16 {17 scanf("%d", &q[i]);18 }19 memset(f, 1, n);//初始化 20 for(register int i = 1; i <= n; ++i)21 {22 for(register int j = 1; j < i; ++j)23 {24 if(q[i] > q[j])//要大于 25 {26 f[i] = max(f[i], f[j] + 1);//取max 27 }28 }29 maxl = max(maxl, f[i]);//取答案最大值 30 }31 printf("%d", maxl);//最后输出的是maxl，不是f[n] 32 return 0;33 }
2. O(n log n)
思路 ：现在不需要整f[i]了，但整一个x数组和z，z表示最长上升子序列的长度，x里存的是最长上升子序列。注意 ：此时要先把x[++z] = q[1]，然后循环2 ~ n，如果当前数 > x[z]那么直接插进去就好了，否则二分查找第一个大于等于它的数，然后把那个数给替换掉，其他的不变，最后输出z。
证明 ：查找出来的数是第一个大于等于它的数，那么当前数肯定比它右边的数要小（因为u（当前数） <= x（第一个比u大的数）&& x < y（x左边的数）所以 u < y）
查找出来的数是第一个大于等于它的数，那么既然是第一个，那一定左面的数就 <= 当前数了呗
code（直接用STL了） ：
1 #include2 using namespace std; 3 int n, q[100001], x[100001], z; 4 int main() 5 { 6 scanf("%d", &n); 7 for(register int i = 1; i <= n; ++i) 8 { 9 scanf("%d", &q[i]);10 }11 x[++z] = q[1];12 for(register int i = 2; i <= n; ++i)13 {14 if(q[i] > x[z])15 {16 x[++z] = q[i];17 }18 else19 {20 int p = lower_bound(x + 1, x + z + 1, q[i]) - x;21 x[p] = q[i];22 }23 }24 printf("%d", z);25 return 0;26 }
二. 关于最长公共子序列
题目大意：给定两个字符串x，y，求两个字符串中最长公共（及两个字符相等）子序列
思路：设f[i][j]表示x序列到第i个字符，y序列到第j个字符的最长公共子序列。这时分两种情况，一是x[i]和y[j]这两个字符相等（及可以同时选），那么答案就 等于f[i - 1][j - 1] + 1了（及从1 ~ i - 1和1 ~ j - 1中选最长公共子序列再加上1，因为还要加上x[i]，y[j]这两个相等个字符啊）；二是x[i] != y[j]（及不能同时选，想同时选也不能同时选啊，都不同怎么同时选），那么这是会比较麻烦，因为我们只能选其一，所以我们就在两种不同的方案里取最大值——f[i][j] = max(f[i][j - 1], f[i - 1][j])。然后……就没有然后了，就完了，直接枚举x序列和y序列的长度，进行判断，看执行哪个，最后输出f[x序列的长度][y序列的长度]就OK了
code：
1 #include2 using namespace std; 3 int n, f[1001][1001]; 4 char x[1001], y[1001]; 5 signed main() 6 { 7 scanf("%s %s", x, y); 8 int lx = strlen(x); 9 int ly = strlen(y);10 for(register int i = 1; i <= lx; ++i)11 {12 for(register int j = 1; j <= ly; ++j)13 {14 if(x[i - 1] == y[j - 1])//从一开始枚举的，要减一才是正确的字符啊 15 {16 f[i][j] = f[i - 1][j - 1] + 1;//别忘了加一 17 }18 else19 {20 f[i][j] = max(f[i - 1][j], f[i][j - 1]);//两种情况取max，从而得到最优值 21 }22 }23 }24 printf("%d", f[lx][ly]);//最后答案在f[lx][ly]里 25 return 0;26 }