拦截导弹 最长上升/下降子序列

题意, 长度为n的序列, a1,a2, ...,ai, ..., an,  求最长严格上升子序列长度,与最长下降非严格自序列长度.

 

解法:     首先不得不吐嘈下题目的读入,恶心指数上达5颗星.

　　对于一套拦截系统最多能拦截多少导弹, 求个非严格下降子序列就可以了.就不废话了. 主要还是求最少拦截数量.

　　有一个结论, 最少拦截系统数量为 严格上升子序列.  思路如下:

　　　　假定一个最长上升子序列形式如:    ...a_i ... aj  ... 

　　　　对于  a_i 与 a_j 之间的数 x 只可能有两类,  x <= a_i , 则可以 将这些导弹划分到 a_i拦截系统, x >= aj, 则可以将这些导弹划分到 a_j拦截系统.

其它区间类似.   其中还有如下情况,    b_1, b_2, <= a_i,  但是  b_1 > b_2,  那么b_1,b_2必定不能归结于一个拦截系统, 但是必定可以被 a_i之前的系统拦截.

　　O(N^2) 代码实现,  

　　　　　令 g( i ), 表示前i个导弹, 取第i个的最大长度.

　　　　　　 dp(i), 表示前i个导弹, 最长上升子序列长度.

　　　　　　g(i) = max( 1, g(j) )   a_i > a_j

　　　　　　dp(i) = max( dp(i-1), g(i) ) 

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std;const int N = 101000;int g[N], dp[N], n, a[N];int main(){n = 0; // scanf("%d", &n); // for(int i = 0; i < n; i++) scanf("%d", a+i ); while( scanf("%d",&a[n] ) != EOF ) n++;dp[0] = 0; for(int i = 1; i <= n; i++){g[i] = 1;for(int j = i-1; j >= 1; j-- )if( a[i-1] <= a[j-1] ) g[i] = max( g[i], g[j]+1 );dp[i] = max( dp[i-1], g[i] ); }printf("%d\n", dp[n] );dp[0] = 0;for(int i = 1; i <= n; i++){g[i] = 1;for(int j = i-1; j >= 1; j-- )if( a[i-1] > a[j-1] ) g[i] = max( g[i], g[j]+1 );dp[i] = max( dp[i-1], g[i] );}printf("%d\n", dp[n] ); return 0; } View Code

　　O(NlogN)的写法,前面写过的题目里头有, 就懒得贴了.

转载于:https://www.cnblogs.com/yefeng1627/archive/2013/05/13/3076890.html

总结

以上是生活随笔为你收集整理的拦截导弹 最长上升/下降子序列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。