洛谷 P1020 导弹拦截(dp+最长上升子序列变形)

传送门:Problem 1020

https://www.cnblogs.com/violet-acmer/p/9852294.html

讲解此题前，先谈谈何为最长上升子序列，以及求法：

一、相关概念

　　1.串 & 子序列

　　　　一个串的子串是指该串的一个连续的局部。

　　　　如果不要求连续，则可称为它的子序列。

　　　　比如对串： "abcdefg" 而言，"ab","abd","bdef" 等都是它的子序列。　　

　　　　特别地，一个串本身，以及空串也是它的子序列。

　　2.最长上升子序列 & 最长不下降子序列

　　　　最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。

　　　　而最长不下降子序列则不一定要保证单调递增，只要保证 a[ i ] <= a[ j ] ( j > i , 且在序列范围内)即可。

二、相关算法：

　　假设数组 a[ ] : 2 5 3 4 1 7 6，求其最长上升子序列长度。

　洛谷 P1020 导弹拦截(dp+最长上升子序列变形)

　　1.朴素算法

　　　　 $n^{2}$

　　　洛谷 P1020 导弹拦截(dp+最长上升子序列变形)

　　　　这种方法就是每一次寻找“可以接下去的”，换句话说

　　　　当 $a_{j} < a_{i} (j < i)$

　　　　对于每一个数，他都是在“可以接下去”的中，从前面的最优值+1转移而来。

　　　　因此，这个算法是可以求出正确答案的。

　　　　复杂度很明显，外层 i 枚举每个数，内层 j 枚举目前 i 的最优值，即O(N^2) $n^{2}$

$n^{2}$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=100;
 4 
 5 int n;
 6 int a[maxn];
 7 int dp[maxn];
 8 
 9 void Solve()
10 {
11     for(int i=1;i <= n;++i)
12         for(int j=i+1;j <= n;++j)
13             dp[j]=(a[j] > a[i] && dp[i]+1 > dp[j] ? dp[i]+1:dp[j]);//判断是否更新 dp[j]
14     for(int i=1;i <= n;++i)
15         printf("%d%c",dp[i],i == n ? '\n':' ');
16 }
17 int main()
18 {
19     scanf("%d",&n);
20     for(int i=1;i <= n;++i)
21         scanf("%d",a+i),dp[i]=1;//初始化 dp[ ]为 1
22     Solve();
23 }

View Code

　　2.O(nlogn)算法

　　详解参看大佬博客%%%%%%%%%%%

　　https://www.cnblogs.com/itlqs/p/5743114.html

现在开始回归主题：

题意：

　　求最长不上升子序列的长度以及这个序列里面最少有多少最长不上升子序列。

题解：

　　对于第一问，和上面所讲的求最长上升子序列思想类似，上面的讲解懂了，第一问也就破了；

　　难点就在与第二问，如何求呢？

　　看大佬博客说“求一个序列里面最少有多少最长不上升序列等于求这个序列里最长上升序列的长度”，我也不懂为啥 /小纠结，或许，这就是大佬吧。

废话少说，上AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define INF 0x3f3f3f3f
 4 const int maxn=1e5+50;
 5 
 6 int n;
 7 int a[maxn];
 8 int dp[maxn];
 9 
10 void Solve()
11 {
12     int len=0;
13     dp[len]=INF;
14     for(int i=1;i <= n;++i)
15     {
16         if(a[i] <= dp[len])
17             dp[++len]=a[i];
18         else
19         {
20             int l=0,r=len+1;
21             while(r-l > 1)//二分出最后一个不小于 a[i] 的下标
22             {
23                 int mid=(l+r)/2;
24                 if(dp[mid] >= a[i])//注意，此处取到"=="判给了 l
25                     l=mid;
26                 else
27                     r=mid;
28             }
29             dp[r]=a[i];
30         }
31     }
32     printf("%d\n",len);
33     len=0;
34     dp[len]=-1;
35     for(int i=1;i <= n;++i)//求最长上升子序列
36     {
37         if(a[i] > dp[len])
38             dp[++len]=a[i];
39         else
40         {
41             int t=lower_bound(dp+1,dp+len+1,a[i])-dp;
42             dp[t]=a[i];
43         }
44     }
45     printf("%d\n",len);
46 }
47 
48 int main()
49 {
50     while(~scanf("%d",&a[++n]))//以回车结束输入的输入方式
51         continue;
52     n--;
53     Solve();
54 }

View Code

　　注意事项：

　　　　(1):输入方式

　　　　正确的输入方式：

1 while(~scanf("%d",&a[++n]))//以回车结束输入的输入方式
2     continue;
3 n--;//最后一个 n 接受的是 '\n' ，所以需要减去

View Code

　　　　错误的输入方式，返回 RE，至今不知道为啥，有知道的大佬可否告知一二%%%%%%%%

1 do
2 {
3     scanf("%d",&a[++n]);
4 }while(getchar() != '\n');

View Code

　　　　第一种输入方式在本地无法测试，但 OJ 可以。

　　　　第二种输入方式，虽然本地可以测试，但提交后返回 RE，应该是输入停不下来的吧。

秒客网

洛谷 P1020 导弹拦截(dp+最长上升子序列变形)

相关文章