Uva 1471 Defense Lines（LIS变形）

题意：

　　给你一个数组，让你删除一个连续的子序列，使得剩下的序列中有最长上升子序列，求出这个长度。

题解：

　　预处理：先求一个last[i]，以a[i]为开始的合法最长上升子序列的长度。再求一个pre[i]，以a[i]为结尾的合法最长上升子序列长度。

　　那么这题的答案就是：max(pre[j]) + last[i]。（j<=a[i] - 1）。

　　例如a[i]为3的话, 答案就是max(以1结尾的LIS长度，以2结尾的LIS长度) + 以3开始LIS长度。

　　dis[i] 是 LIS 长度为i的时候，最小的a[i]。（详细请看LIS nlogn算法）

　　所以

　　len = (lower_bound(dis+1, dis+1+i, a[i]) - (dis+1)) + last[i]。//二分查找

　　ans = max (ans, len);

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 //#define LOCAL

 #define eps 0.0000001

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x7fffffff;

 const int maxn = +;

 const int mod = ;

 int a[maxn];

 int last[maxn];

 int pre[maxn];

 int dis[maxn];

 void solve()

 {

     int n;

     scanf("%d", &n);

     for(int i=;i<=n;i++)    scanf("%d", &a[i]);

     ms(pre, );

     ms(last, );

     last[n] = ;

     for(int i=n-;i>;i--){

         if(a[i] < a[i+]){

             last[i] = last[i+] + ;

         }else last[i] = ;

     }

     pre[] = ;

     for(int i= ;i<=n;i++){

         if(a[i] > a[i-]){

             pre[i] = pre[i-] + ;

         }else pre[i] = ;

     }

     for(int i=;i<=n;i++)   dis[i] = inf;

     int ans = ;

     for(int i=;i<=n;i++){

         int len = (lower_bound(dis+, dis++i, a[i]) -(dis+))+ last[i];

         ans = max(ans, len);

         dis[pre[i]] = min(a[i], dis[pre[i]]);

     }

     printf("%d\n", ans);

 }

 int main() {

 #ifdef LOCAL

     freopen("jumping.in", "r", stdin);

 //      freopen("output.txt", "w", stdout);

 #endif // LOCAL

     int t;

     scanf("%d", &t);

     while(t--){

         solve();

     }

     return ;

 }

巴特西

Uva 1471 Defense Lines（LIS变形）

最新文章

热门文章