CSU - 1551 Longest Increasing Subsequence Again —— 线段树/树状数组 + 前缀和&后缀和

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1551

题意：

给出一段序列，删除其中一段连续的子序列（或者不删），使得剩下的序列的最长上升连续子序列最大。

题解：

1.对于要删除的的子序列而言，要么夹在答案序列中间，要么在外面（删与不删对答案都没影响）。所以总体而言，答案序列被分成左右两半。

2.用SL[i]记录从左边起以a[i]为结尾的最长上升连续子序列的长度， SR记录从右边起以a[i]为开始的最长上升连续子序列的长度。

3.枚举SR[i]，用线段树找出最大的SL[x]（x的下标小于i），即SL[x]和SR[x]构成一段完整的序列，期间一直更新线段树。

学习之处：

1.线段树/树状数组的动态使用，即边查询边更新。

类似的题： http://blog.csdn.net/DOLFAMINGO/article/details/65643894

2.RMQ/线段树/树状数组的静态使用，即build()之后值进行查询操作。

线段树：

 #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 eps 0.0000001

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int maxn = +;

 int a[maxn], SL[maxn], SR[maxn], MAX[maxn<<];

 int n;

 void update(int rt, int l, int r, int pos)

 {

     if(l==r)

     {

         MAX[rt] = max(MAX[rt], SL[pos]);

         return;

     }

     int mid = (l+r)>>;

     if(a[pos]<=mid) update(rt*, l, mid, pos);

     else update(rt*+ ,mid+, r, pos);

     MAX[rt] = max(MAX[rt*], MAX[rt*+]);

 }

 int query(int rt, int l, int r, int x, int y)

 {

     if(x<=l && y>= r)

         return MAX[rt];

     int mid = (l+r)>>, ret = ;

     if(x<=mid) ret = max(ret, query(rt*, l, mid, x, y));

     if(y>=mid+) ret = max(ret, query(rt*+, mid+, r, x, y));

     return ret;

 }

 void solve()

 {

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

         scanf("%d",&a[i]);

     SL[] = SR[n] = ;

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

         SL[i] = (a[i]>a[i-]?SL[i-]+:);

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

         SR[i] = (a[i]<a[i+]?SR[i+]+:);

     int ans = ;

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

     {

         int tmp = ;

         if(a[i]>) tmp = query(, , , , a[i]-);

         ans = max(ans,SR[i]+tmp);

         update(, , , i);

     }

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

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         ms(SL,);

         ms(SR,);

         ms(MAX,);

         solve();

     }

 }

树状数组：

 #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 eps 0.0000001

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int maxn = +;

 int a[maxn], SL[maxn], SR[maxn], c[maxn];

 int n;

 int lowbit(int x)

 {

     return x&(-x);

 }

 void add(int x, int d)

 {

     while(x<maxn)

     {

         c[x] = max(c[x],d);

         x += lowbit(x);

     }

 }

 int sumc(int x)

 {

     int s = ;

     while(x>)

     {

         s = max(s,c[x]);

         x -= lowbit(x);

     }

     return s;

 }

 void solve()

 {

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

         scanf("%d",&a[i]);

     SL[] = SR[n] = ;

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

         SL[i] = (a[i]>a[i-]?SL[i-]+:);

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

         SR[i] = (a[i]<a[i+]?SR[i+]+:);

     int ans = ;

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

     {

         int tmp = ;

         if(a[i]>) tmp = sumc(a[i]-);

         ans = max(ans,SR[i]+tmp);

         add(a[i],SL[i]);

     }

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

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF)

     {

         ms(SL,);

         ms(SR,);

         ms(c,);

         solve();

     }

 }

巴特西

CSU - 1551 Longest Increasing Subsequence Again —— 线段树/树状数组 + 前缀和&后缀和

最新文章

热门文章