Improvements

NC54477. Improvements

描述

Son Halo owns n spaceships numbered from 1 to n and a space station. They are initially placed on one line with the space station so the spaceship i is positioned x_i meters from the station and all ships are on the same side from the station (x_i > 0). All x_i are distinct. Station is considered to have number 0 and x₀ is considered to be equal to 0.

Every two spaceships with consequent numbers are connected by a rope, and the first one is connected to the station. The rope number i (for 1 ≤ i ≤ n) connects ships i and i−1. Note, that the rope number 1 connects the first ship to the station.

Son Halo considers that the rope i and the rope j intersect when the segments $[x^{min}_i, x^{max}_i]$ and $[x^{min}_j, x^{max}_j]$ have common internal point but neither one of them is completely contained in the other, where $x^{min}_{k} = \min (x_{k-1}, x_{k})$ , $x^{max}_{k} = \max (x_{k-1}, x_{k})$ .

$\left[ \begin{array}{l} x^{min}_{i} < x^{min}_{j} \text{ \& } x^{min}_{j} < x^{max}_{i} \text{ \& } x^{max}_{i} < x^{max}_{j} \\ x^{min}_{j} < x^{min}_{i} \text{ \& } x^{min}_{i} < x^{max}_{j} \text{ \& } x^{max}_{j} < x^{max}_{i} \end{array} \right.$
Son Halo wants to rearrange spaceships in such a way, that there are no rope intersections. Because he is lazy, he wants to rearrange the ships in such a way, that the total number of ships that remain at their original position x_i is maximal. All the ships must stay on the same side of the station and at different positions x_i after rearrangement. However, ships can occupy any real positions x_i after rearrangement.

Your task is to figure out what is the maximal number of ships that can remain at their initial positions.

输入描述

The first line of the input file contains n (1 ≤ n ≤ 200 000) — the number of ships. The following line contains n distinct integers x_i (1 ≤ x_i ≤ n) — the initial positions of the spaceships.

输出描述

The output file must contain one integer — the maximal number of ships that can remain at their initial positions in the solution of this problem.

示例1

输入:

4
1 3 2 4

输出:

说明:

In the first sample Son Halo can move the second spaceship in the position between the first and the third to solve the problem while keeping 3 other ships at their initial positions.

示例2

输入:

4
1 4 2 3

输出:

说明:

In the second sample there are no rope intersections, so all 4 ships can be left at their initial positions.

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 38ms, 内存消耗: 5656K, 提交时间: 2020-10-12 20:10:14

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int f[N],g[N],a[N];
int tf[N],tg[N],n;
inline void add1(int x,int y){
	while(x<=n)tf[x]=max(tf[x],y),x+=x&-x;
}
inline void add2(int x,int y){
	while(x>=1)tg[x]=max(tg[x],y),x-=x&-x;
}
inline int query1(int x){
	int ans=0;
	while(x>=1)ans=max(ans,tf[x]),x-=x&-x;
	return ans;
}
inline int query2(int x){
	int ans=0;
	while(x<=n)ans=max(ans,tg[x]),x+=x&-x;
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	int mx=0;
	for(int i=1;i<=n;++i){
		f[i]=query1(a[i]-1)+1;
		g[i]=query2(a[i]+1)+1;
		add1(a[i],f[i]);add2(a[i],g[i]);
		mx=max(mx,f[i]+g[i]-1);
	}
	cout<<mx;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 108ms, 内存消耗: 84628K, 提交时间: 2020-10-09 12:36:55

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=1e7+10;
const int inf=0x3f3f3f3f;
int n,m,k;
int a[N];
int f[N],g1[N],g2[N];
signed main(){
    cin>>n;
    int x;
    for(int i=0;i<n;i++){
        scanf("%d",&x);a[x-1]=i;
    }
    memset(f,inf,sizeof f);
    for (int i=0;i<n;i++) {
        int k=lower_bound(f,f+n,a[i])-f;
        f[k]=a[i];g1[i]=k+1;
    }
    reverse(a,a+n);
    memset(f,inf,sizeof f);
    for (int i=0;i<n;i++) {
        int k=lower_bound(f,f+n,a[i])-f;
        f[k]=a[i];g2[i]=k+1;
    }
    int mx=0;
    for (int i=0;i<n;i++){
        mx=max(mx,g1[i]+g2[n-i-1]-1);
    }
    cout<<mx<<endl;
    return 0;
}