UVALive 6947 Improvements（DP+树状数组）
【题目链接】
【题目大意】
给出一些飞船的位置，每艘飞船用绳子和序号相邻的飞船相连，现在去掉一些飞船，使得飞船之间的绳子不交叉。
【题解】
绳子不交叉的情况就是可以有两条不交叉的路线来回，我们将位置序列转化为以位置为下标的编号序列，那么题目就转化为求先增后减的最长序列，那么，我们dp正反各求一遍LIS，保存在每个位置，将每个位置两次的答案求和，取最大值就是答案了。
【代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200005;
int n,x,a[N],c[N],up[N],down[N];
int add(int x,int num){while(x<N)c[x]=max(c[x],num),x+=x&-x;}
int query(int x){int s=0;while(x)s=max(s,c[x]),x-=x&-x;return s;}
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++)scanf("%d",&x),a[x]=i;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)add(a[i],up[i]=query(a[i])+1);
memset(c,0,sizeof(c));
for(int i=n;i;i--)add(a[i],down[i]=query(a[i])+1);
int ans=0;
for(int i=1;i<=n;i++)ans=max(up[i]+down[i]-1,ans);
printf("%d\n",ans);
}return 0;
}
评论 (0)
