1017. 怪盗基德的滑翔翼
怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。
而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。
不得已，怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。
初始时，怪盗基德可以在任何一幢建筑的顶端。
他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。
因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。
他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。
请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？
输入格式
输入数据第一行是一个整数K，代表有K组测试数据。
每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按照建筑的排列顺序给出。
输出格式
对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。
数据范围
1≤K≤1001≤K≤100,
1≤N≤1001≤N≤100,
0<h<100000<h<10000输入样例：
3 8 300 207 155 299 298 170 158 65 8 65 158 170 298 299 155 207 300 10 2 1 3 4 5 6 7 8 9 10输出样例：
6 6 9
分析：
显然，这是一道很裸的最长上升子序问题。
我们只需要先正着做一遍最长上升子序，然后将数组翻转在做一遍最长上升子序就OK了
代码：
1 //那就是求一遍最长上升子序，然后将数组翻转再求一边最长上升子序 2 #include <bits/stdc++.h> 3 using namespace std; 4 5 const int N = 110; 6 7 int n; 8 int w[N]; 9 int f[N]; 10 11 void work() 12 { 13 cin >> n; 14 15 int ans = 0; 16 for (int i = 1; i <= n; i ++ ) 17 { 18 cin >> w[i]; 19 f[i] = 1; 20 for (int j = 1; j < i; j ++ ) 21 if (w[i] > w[j]) 22 f[i] = max(f[i], f[j] + 1); 23 24 ans = max(f[i], ans); 25 } 26 27 reverse(w + 1, w + 1 + n); 28 29 for (int i = 1; i <= n; i ++ ) 30 { 31 f[i] = 1; 32 for (int j = 1; j < i; j ++ ) 33 if (w[i] > w[j]) 34 f[i] = max(f[i], f[j] + 1); 35 36 ans = max(f[i], ans); 37 } 38 39 cout << ans << endl; 40 } 41 int main() 42 { 43 int T; cin >> T; 44 while (T -- ) 45 { 46 work(); 47 } 48 }
1014. 登山
五一到了，ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。
队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？
输入格式
第一行包含整数N，表示景点数量。
第二行包含N个整数，表示每个景点的海拔。
输出格式
输出一个整数，表示最多能浏览的景点数。
数据范围
2≤N≤10002≤N≤1000
输入样例：
8 186 186 150 200 160 130 197 220输出样例：
4
分析：
还是一道裸的单调上升子序问题，正着求一边，倒着求一边。
代码：
1 //正着求一遍最长上升子序并存起来，反着求一边最长上升子序，并计算总序列长度 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 1010; 7 8 int n; 9 int a[N]; 10 int f[N], g[N]; 11 int ans; 12 13 int main() 14 { 15 cin >> n; 16 for (int i = 1; i <= n; i ++ ) cin >> a[i]; 17 18 for (int i = 1; i <= n; i ++ ) 19 { 20 f[i] = 1; 21 for (int j = 1; j < i; j ++ ) 22 if (a[i] > a[j]) 23 f[i] = max(f[i], f[j] + 1); 24 } 25 26 for (int i = n; i >= 1; i -- ) 27 { 28 g[i] = 1; 29 for (int j = n; j > i; j -- ) 30 if (a[i] > a[j]) 31 g[i] = max(g[i], g[j] + 1); 32 33 ans = max(ans, f[i] + g[i] - 1); 34 } 35 36 cout << ans << endl; 37 38 return 0; 39 }
482. 合唱队形
题目：
NN 位同学站成一排，音乐老师要请其中的 (N−K)(N−K) 位同学出列，使得剩下的 KK 位同学排成合唱队形。
合唱队形是指这样的一种队形：设 KK 位同学从左到右依次编号为 1，2…，K1，2…，K，他们的身高分别为 T1，T2，…，TKT1，T2，…，TK， 则他们的身高满足 T1<…<Ti>Ti+1>…>TK(1≤i≤K)T1<…<Ti>Ti+1>…>TK(1≤i≤K)。
你的任务是，已知所有 NN 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入格式
输入的第一行是一个整数 NN，表示同学的总数。
第二行有 NN 个整数，用空格分隔，第 ii 个整数 TiTi 是第 ii 位同学的身高(厘米)。
输出格式
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
数据范围
2≤N≤1002≤N≤100,
130≤Ti≤230130≤Ti≤230输入样例：
8 186 186 150 200 160 130 197 220输出样例：
4
分析
裸题，最长上升子序，正反来一下
代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int N = 110; 6 7 int n; 8 int a[N]; 9 int f[N], g[N]; 10 11 int main() 12 { 13 cin >> n; 14 15 for (int i = 1; i <= n; i ++ ) 16 { 17 f[i] = 1; 18 cin >> a[i]; 19 for (int j = 1; j < i; j ++ ) 20 if (a[i] > a[j]) 21 f[i] = max(f[i], f[j] + 1); 22 } 23 24 int ans = 0; 25 for (int i = n; i >= 1; i -- ) 26 { 27 g[i] = 1; 28 for (int j = n; j > i; j -- ) 29 if (a[i] > a[j]) 30 g[i] = max(g[i], g[j] + 1); 31 32 ans = max(ans, f[i] + g[i] - 1); 33 } 34 35 cout << n - ans << endl; 36 37 return 0; 38 }
1012. 友好城市
题目：
Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。
北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。
每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。
编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。
输入格式
第1行，一个整数N，表示城市数。
第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。
输出格式
仅一行，输出一个整数，表示政府所能批准的最多申请数。
数据范围
1≤N≤50001≤N≤5000,
0≤xi≤100000≤xi≤10000输入样例：
7 22 4 2 6 10 3 15 12 9 8 17 17 4 2输出样例：
4
分析：
又是一个裸的最长上升子序问题，我们发现，将一条边按照升序排序，另一边的求一下最长上升子序就OK了。
为什么呢？为什么这么想呢？
首先，这题和顺序无关，（排布排序对题目结果无影响），那么我们就给他排个序。
我们发现，只有当递增的时候，才不会有交叉，如果出现交叉，就不合法了，那么，很显然，求最长上升子序。
代码：
1 //这不还是求最长单调上升子序嘛 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 5010; 7 8 struct Node 9 { 10 int x, y; 11 12 bool operator< (const Node &W) const 13 { 14 return x < W.x; 15 } 16 }a[N]; 17 18 int n; 19 int f[N]; 20 21 int main() 22 { 23 cin >> n; 24 for (int i = 1; i <= n; i ++ ) 25 { 26 int x, y; cin >> x >> y; 27 a[i] = {x, y}; 28 } 29 30 sort(a + 1, a + n + 1); 31 32 // for (int i = 1; i <= n; i ++ ) cout << a[i].x << ' ' << a[i].y << endl; 33 int ans = 0; 34 for (int i = 1; i <= n; i ++ ) 35 { 36 f[i] = 1; 37 for (int j = 1; j < i; j ++ ) 38 if (a[i].y > a[j].y) 39 f[i] = max(f[i], f[j] + 1); 40 ans = max(ans, f[i]); 41 } 42 43 cout << ans << endl; 44 45 return 0; 46 }
1016. 最大上升子序列和
一个数的序列 bibi，当 b1<b2<…<bSb1<b2<…<bS 的时候，我们称这个序列是上升的。
对于给定的一个序列(a1,a2,…,aNa1,a2,…,aN)，我们可以得到一些上升的子序列(ai1,ai2,…,aiKai1,ai2,…,aiK)，这里1≤i1<i2<…<iK≤N1≤i1<i2<…<iK≤N。
比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。
这些子序列中和最大为18，为子序列(1,3,5,9)的和。
你的任务，就是对于给定的序列，求出最大上升子序列和。
注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。
输入格式
输入的第一行是序列的长度N。
第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。
输出格式
输出一个整数，表示最大上升子序列和。
数据范围
1≤N≤10001≤N≤1000
输入样例：
7 1 7 3 5 9 4 8输出样例：
18
分析：
还是裸的最长上升子序的题，只不过将这里维护的信息变成了和的最大值，而不是长度
代码：
1 //大概还是模板吧，现在维护的不再是长度了，而是最大值，更换下属性就OK了吧 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 1010; 7 8 int n; 9 int w[N]; 10 int f[N]; 11 12 int main() 13 { 14 cin >> n; 15 int ans = 0; 16 for (int i = 1; i <= n; i ++ ) 17 { 18 cin >> w[i]; 19 f[i] = w[i]; 20 for (int j = 1; j < i; j ++ ) 21 if (w[i] > w[j]) 22 f[i] = max(f[i], f[j] + w[i]); 23 24 ans = max(ans, f[i]); 25 } 26 27 cout << ans << endl; 28 29 return 0; 30 }
1010. 拦截导弹
题目
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行，输入导弹依次飞来的高度。
输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。
数据范围
雷达给出的高度数据是不大于 3000030000 的正整数，导弹数不超过 10001000。
输入样例：
389 207 155 300 299 170 158 65输出样例：
6 2
分析：
第一问就是最长上升子序的小变形，第二个就是一个贪心的思想。
第一个不用多说，很直白，第二问，就是最贪心的考虑，如果有一个拦截导弹的现有高度大于等于当前导弹高度，那就可以拦截他。
我们贪心的考虑，尽可能用更少的拦截导弹，也就是让拦截导弹拦截的更多，那就将他放到一个大于等于导弹高度的，且所有拦截导弹中最小的一个就OK了。如果不存在就开一个新的拦截导弹。
代码：
1 //最长下降子序，加上二分一下最小的大于当前数的值，并替换 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 1010; 7 8 int n; 9 int a[N]; 10 int f[N]; 11 int q[N]; 12 int main() 13 { 14 string line; 15 getline(cin, line); 16 stringstream ssin(line); 17 while (ssin >> a[++ n]); 18 19 // for (int i = 0; i <= n; i ++ ) cout << a[i] << ' '; 20 // cout << endl; 21 int ans = 0; 22 for (int i = 1; i <= n; i ++ ) { 23 for (int j = 1; j < i; j ++ ) 24 if (a[i] <= a[j]) 25 f[i] = max(f[i], f[j] + 1); 26 ans = max(ans, f[i]); 27 } 28 29 //思想，就是替换掉大于等于他的第一个数，如果没有比他大的，就新开一个 30 int cnt = 0; 31 for (int i = 1; i <= n; i ++ ) 32 { 33 if (i == 1) q[cnt ++ ] = a[i]; 34 else 35 { 36 int pos = lower_bound(q, q + cnt, a[i]) - q; 37 // cout << pos << ' ' << cnt << ' ' << q[pos] << endl; 38 if (pos >= cnt) q[cnt ++ ] = a[i]; 39 else q[pos] = a[i]; 40 } 41 } 42 cout << ans << endl; 43 cout << cnt << endl; 44 }
187. 导弹防御系统
题目：
为了对抗附近恶意国家的威胁，RR 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如，一套系统先后拦截了高度为 33 和高度为 44 的两发导弹，那么接下来该系统就只能拦截高度大于 44 的导弹。
给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例，第一行包含整数 nn，表示来袭导弹数量。
第二行包含 nn 个不同的整数，表示每个导弹的高度。
当输入测试用例 n=0n=0 时，表示输入终止，且该用例无需处理。
输出格式
对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。
数据范围
1≤n≤501≤n≤50
输入样例：
5 3 5 2 4 1 0输出样例：
2样例解释
对于给出样例，最少需要两套防御系统。
一套击落高度为 3,43,4 的导弹，另一套击落高度为 5,2,15,2,1 的导弹。
分析：
这一题有上一题变形而来，不再是只有拦截单调下降的防御系统了，而是可以拦截单调上升的或者拦截单调下降的两种情况。
那么我们可以用贪心的思想，每次尝试将当前高度的导弹，放到单调上升和单调下降的防御系统中。
然后，分别看，当前导弹需要新开辟一个系统还是放在已有的系统中。
这个过程需要贪心来考虑。
代码：
1 //就是问一个序列可以拆分成最少多少个子序列，这些子序列的合法条件是，要么严格单调上升，要么严格单调下降 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 6 const int N = 60; 7 8 int n; 9 int a[N]; 10 int up[N], down[N]; 11 //up是单调递减的，down是单调递增的 12 bool dfs(int depth, int u, int su, int sd) 13 { 14 if (depth < su + sd) return false; 15 if (u == n) return true; 16 17 bool flag = true; 18 for (int i = 1; i <= su; i ++ ) 19 if (up[i] < a[u]) 20 { 21 int t = up[i]; 22 up[i] = a[u]; 23 if (dfs(depth, u + 1, su, sd)) return true; 24 up[i] = t; 25 flag = false; 26 break; 27 } 28 29 if (flag) 30 { 31 up[su + 1] = a[u]; 32 if (dfs(depth, u + 1, su + 1, sd)) return true; 33 } 34 35 flag = true; 36 for (int i = 1; i <= sd; i ++ ) 37 if (down[i] > a[u]) 38 { 39 int t = down[i]; 40 down[i] = a[u]; 41 if (dfs(depth, u + 1, su, sd)) return true; 42 down[i] = t; 43 flag = false; 44 break; 45 } 46 if (flag) 47 { 48 down[sd + 1] = a[u]; 49 if (dfs(depth, u + 1, su, sd + 1)) return true; 50 } 51 return false; 52 } 53 void work() 54 { 55 for (int i = 0; i < n; i ++ ) cin >> a[i]; 56 57 //迭代加深，depth为导弹总数 58 int depth = 0; 59 while(!dfs(depth, 0, 0, 0)) depth ++ ; 60 cout << depth << endl; 61 } 62 63 int main() 64 { 65 while (cin >> n, n) 66 { 67 work(); 68 } 69 return 0; 70 }
272. 最长公共上升子序列
题目：
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。
小沐沐说，对于两个数列 AA 和 BB，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过，只要告诉奶牛它的长度就可以了。
数列 AA 和 BB 的长度均不超过 30003000。
输入格式
第一行包含一个整数 NN，表示数列 A，BA，B 的长度。
第二行包含 NN 个整数，表示数列 AA。
第三行包含 NN 个整数，表示数列 BB。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
数据范围
1≤N≤30001≤N≤3000,序列中的数字均不超过 231−1231−1。
输入样例：
4 2 2 1 3 2 1 2 3输出样例：
2
分析：
这个题目，是最长上升子序列和最长公共子序列的结合题。
我们可以将这个题按照这两个题目的要求，将三重循环给写出来，然后我们可以通过观察状态转移来讲代码优化到二重循环。
代码：
最长公共字串的代码
1 //为了更好的联系知识点，这里先放入我们最长公共字串的代码 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int N = 1010; 10 11 int n, m; 12 char a[N], b[N]; 13 int f[N][N];//表示字符串a以i结尾，字符转以j结尾的最长的匹配长度 14 15 int main() 16 { 17 cin >> n >> m; 18 cin >> a + 1 >> b + 1; 19 20 for (int i = 1; i <= n; i ++ ) 21 { 22 for (int j = 1; j <= m; j ++ ) 23 { 24 if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1); 25 else f[i][j] = max(f[i - 1][j], f[i][j - 1]); 26 } 27 } 28 29 cout << f[n][m] << endl; 30 31 return 0; 32 }
最长上升子序列的代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int N = 1010; 9 10 int n; 11 int a[N]; 12 int f[N];//含义：表示以i结尾的最长上升子序列的最长长度 13 14 int main() 15 { 16 cin >> n; 17 18 int ans = 0; 19 for (int i = 1; i <= n; i ++ ) 20 { 21 cin >> a[i]; 22 f[i] = 1; 23 for (int j = 1; j < i; j ++ ) 24 if (a[i] > a[j]) 25 f[i] = max(f[i], f[j] + 1); 26 ans = max(ans, f[i]); 27 } 28 29 cout << ans << endl; 30 31 return 0; 32 }
最长公共上升子序列
三for代码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int N = 3010; 9 10 int n; 11 int a[N], b[N]; 12 int f[N][N]; 13 14 int main() 15 { 16 cin >> n; 17 for (int i = 1; i <= n; i ++ ) cin >> a[i]; 18 for (int i = 1; i <= n; i ++ ) cin >> b[i]; 19 20 for (int i = 1; i <= n; i ++ ) 21 for (int j = 1; j <= n; j ++ ) 22 if (a[i] == b[j]) 23 { 24 for (int k = 0; k < j; k ++ )//从0开始，相当于表示当前f为1了 25 if (b[k] < a[i]) 26 f[i][j] = max(f[i][j], f[i - 1][k] + 1); 27 } 28 else f[i][j] = f[i - 1][j]; 29 30 int ans = 0; 31 for (int i = 1; i <= n; i ++ ) 32 ans = max(ans, f[n][i]); 33 cout << ans << endl; 34 return 0; 35 }
二for代码
在三for代码中，我们发现第三重for循环，是基于当出现a[i] == b[j]的时候，然后，k从b[0]遍历到了b[j-1]，找到了f[i][1~j-1]的最大值。
我们发现，第二层循环j从1到n的时候，第一层循环i是一个定值，所以条件b[k]<a[i]是固定的。因此当j增加1的时候，k的范围也是只是
从1<=k<j变到了0<=k<j+1，所以我们只需要O(1)的检查整数j是否会进入决策集合就OK了，那么我们用一个数val，表示每一次决策的时候
当前的1~j-1的最大值就OK了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int N = 3010; 9 10 int n; 11 int a[N], b[N]; 12 int f[N][N];//含义：表示以a[i]结尾的，第二维以b[j]结尾的最长公共上升子串的长度 13 14 int main() 15 { 16 cin >> n; 17 for (int i = 1; i <= n; i ++ ) cin >> a[i]; 18 for (int i = 1; i <= n; i ++ ) cin >> b[i]; 19 20 for (int i = 1; i <= n; i ++ ) 21 { 22 int val = f[i - 1][0]; 23 for (int j = 1; j <= n; j ++ ) 24 { 25 //最长公共子串 26 if (a[i] == b[j]) f[i][j] = val + 1; 27 else f[i][j] = f[i - 1][j]; 28 //找到最大的val，最长上升子串 29 if (b[j] < a[i]) val = max(val, f[i - 1][j]); 30 } 31 } 32 33 int ans = 0; 34 for (int i = 1; i <= n; i ++ ) ans = max(ans, f[n][i]); 35 cout << ans << endl; 36 37 return 0; 38 }