备战蓝桥杯Day8（最长上升子序列LIS模型）

1281：最长上升子序列

【题目描述】

一个数的序列bi��，当b1<b2<...<bS�1<�2<...<��的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN)(�1,�2,...,��)，我们可以得到一些上升的子序列(ai1,ai2,...,aiK)(��1,��2,...,���)，这里1≤i1<i2<...<iK≤N1≤�1<�2<...<��≤�。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,8)。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

【输入】

输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

【输出】

最长上升子序列的长度。

【输入样例】

7 1 7 3 5 9 4 8

【输出样例】

4

思路 状态：dp[i]--以第i个元素为结尾的最长上升子序列的长度 状态转移方程：dp[i]=max(dp[i],dp[j]+1)

#include<iostream> using namespace std; #include <limits.h> const int N=1e3+10; int a[N]; int dp[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; dp[i] = 1; } int mx = INT_MIN; for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { if (a[j] < a[i]) dp[i] = max(dp[i],dp[j]+1); } mx = max(mx, dp[i]); } cout << mx; return 0; } 1259：【例9.3】求最长不下降序列

【题目描述】

设有由n(1≤n≤200)�(1≤�≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)�(1)、�(2)、……、�(�)若存在i1<i2<i3<…<ie�1<�2<�3<…<�� 且有b(i1)<=b(i2)<=…<=b(ie)�(�1)<=�(�2)<=…<=�(��)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为77的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为88的不下降序列。

【输入】

第一行为n�,第二行为用空格隔开的n�个整数。

【输出】

第一行为输出最大个数max���(形式见样例)；

第二行为max���个整数形成的不下降序列,答案可能不唯一，输出一种就可以了，本题进行特殊评测。

【输入样例】

14 13 7 9 16 38 24 37 18 44 19 21 22 63 15

【输出样例】

max=8 7 9 16 18 19 21 22 63

 思路

最长不下降子序列 1.状态  dp[i] 以第i个元素作为结尾的最长不下降子序列的长度 2.状态转移方程  if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1)

最后用递归打印pre数组前驱节点

#include<iostream> using namespace std; const int N = 1e3 + 10; int a[N], dp[N],pre[N]; void print(int x) { if (x == 0) return; print(pre[x]); cout << a[x] << " "; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; dp[i] = 1;//边界，每一个元素自身构成最长上升 } int mx = 1, maxId = 1; for (int i = 2; i <= n; i++) { //使用j遍历第i个元素之前的所有元素 for (int j = 1; j < i; j++) { //找到a[j]和a[i]构成上升的情况 if (a[j] <= a[i]) { //dp[i] = max(dp[i], dp[j] + 1); if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; pre[i] = j; } } } //mx = max(mx, dp[i]); if (dp[i] > mx) { mx = dp[i]; maxId = i; } } cout <<"max="<< mx << endl; print(maxId); return 0; } 1264：【例9.8】合唱队形

【题目描述】

N�位同学站成一排，音乐老师要请其中的(N−K)(�−�)位同学出列，使得剩下的K�位同学排成合唱队形。

合唱队形是指这样的一种队形：设K�位同学从左到右依次编号为1,2,…,K1,2,…,�，他们的身高分别为T1,T2,…,TK�1,�2,…,��，则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)�1<�2<…<��,��>��+1>…>��(1≤�≤�)。

你的任务是，已知所有N�位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入】

输入的第一行是一个整数N（2≤N≤100）�（2≤�≤100），表示同学的总数。第二行有n�个整数，用空格分隔，第i�个整数Ti（130≤Ti≤230）��（130≤��≤230）是第i�位同学的身高（厘米）。

【输出】

输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【输入样例】

8 186 186 150 200 160 130 197 220

【输出样例】

4

【提示】

对于50%的数据，保证有n≤20�≤20；

对于全部的数据，保证有n≤100�≤100。

思路：

一个数组记录最大上升子序列长度

一个数字记录最大下降子序列的长度

最后将两个数组相加-1（i被加了两次）求最大值就是队形的长度

总的人数-队形长度即为需要出列的人数 

#include<iostream> using namespace std; const int N = 1e2 + 10; int a[N], dp_up[N], dp_down[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; dp_up[i] = dp_down[i] = 1; } for (int i = 1; i <= n; i++) for (int j = 1; j < i; j++) if (a[j] < a[i]) dp_up[i] = max(dp_up[j] + 1, dp_up[i]); for (int i = n; i >= 1; i--) for (int j = i+1; j <=n; j++) if (a[j] < a[i]) dp_down[i] = max(dp_down[j] + 1, dp_down[i]); int mx = 1; for (int i = 1; i <= n; i++) mx = max(dp_up[i] + dp_down[i] - 1, mx); cout << n - mx << endl; return 0; } 1260：【例9.4】拦截导弹(Noip1999)

【题目描述】

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【输入】

输入导弹依次飞来的高度。

【输出】

第一行：最多能拦截的导弹数；

第二行：要拦截所有导弹最少要配备的系统数。

【输入样例】

389 207 155 300 299 170 158 65

【输出样例】

6 2

思路

输出是求最长不上升子序列（有=的情况注意判断）和最长下降子序列

#include<iostream> using namespace std; #include <limits.h> const int N=1e3+10; int a[N]; int dp_up[N]; int dp_down[N]; int main() { int x; int n = 0; while (cin >> a[++n]) { dp_down[n] = dp_up[n] = 1; } n--;//有^z会多记录一个 for (int i = n; i >= 1; i--) { for (int j = i + 1; j <= n; j++) { if (a[j] <= a[i]) dp_down[i] = max(dp_down[j]+1,dp_down[i]); } } for (int i = 1; i <=n; i++) { for (int j = 1; j <= i; j++) { if (a[j] < a[i]) dp_up[i] = max(dp_up[j]+1,dp_up[i]); } } int mx1 = INT_MIN; int mx2 = INT_MIN; for (int i = 1; i <= n; i++) { mx1 = max(mx1,dp_down[i]); mx2 = max(mx2,dp_up[i]); } cout << mx1 << endl << mx2; return 0; } 1285：最大上升子序列和

【题目描述】

一个数的序列bi��，当b1<b2<...<bS�1<�2<...<��的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN)(�1,�2,...,��)，我们可以得到一些上升的子序列(ai1,ai2,...,aiK)(��1,��2,...,���)，这里1<=i1<i2<...<iK<=N1<=�1<�2<...<��<=�。比如，对于序列(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(1<=N<=1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。

【输出】

最大上升子序列和。

【输入样例】

7 1 7 3 5 9 4 8

【输出样例】

18

思路：求最大上升子序列长度的基础上将+i换成+a[i] 

#include<iostream> using namespace std; #include <limits.h> const int N=1e3+10; int a[N]; int dp[N]; int main() { int n, mxSum = 0; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) { dp[i] = a[i]; for (int j = 1; j < i; ++j) { if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + a[i]); } } for (int i = 1; i <= n; ++i) mxSum = max(mxSum, dp[i]); cout << mxSum; return 0; } 1283：登山

【题目描述】

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

【输入】

第一行：N (2 <= N <= 1000) 景点数;

第二行：N个整数，每个景点的海拔。

【输出】

最多能浏览的景点数。

【输入样例】

8 186 186 150 200 160 130 197 220

【输出样例】

4

思路：就是合唱队形那题一个模型

#include<iostream> using namespace std; #include <limits.h> const int N=1e3+10; int a[N]; int dp_up[N]; int dp_down[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; dp_up[i]=dp_down[i] = 1; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { if (a[j] < a[i]) dp_up[i] = max(dp_up[i], dp_up[j] + 1); } } for (int i=n;i>=1;i--) { for (int j =i+1; j <=n; ++j) { if (a[j] < a[i]) dp_down[i] = max(dp_down[i], dp_down[j] + 1); } } int mx = 1; for (int i = 1; i <= n; i++) { mx = max(mx,dp_up[i]+dp_down[i]-1); } cout << mx; return 0; }