题解 CF1409E 【Subsequences of Length Two】
kradcigam
2020-09-05 15:18:25
写篇题解庆祝我第 $1$ 次参加 $div3$，而且还 $AK$ 了
我们发现 $y$ 坐标越低越好，所以答案与 $y$ 坐标无关。
现在问题等价于一条数轴上有 $n$ 个点，求 $2$ 条线段覆盖尽可能多的点.
我们考虑类似于[双子序列最大和](https://www.luogu.com.cn/problem/P2642)一样的[做法](https://www.luogu.com.cn/blog/180242/solution-p2642)
首先，有 $2$ 个结论：
- $2$ 条线段重叠明显是不优的，我们就需要让这两条无重叠。
- 线段的至少 $1$ 的端点要是 $n$ 个点当中的一个，这样显然会比线段 $2$ 段都不是 $n$ 个中的一个的要优。
这样就可以了
代码：
```cpp
int work(){
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
memset(k,0,sizeof(k));
int n,k;read(n);read(k);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<=n;i++)read(b[i]);
sort(a+1,a+n+1);//不要忘了排序
for(int i=1;i<=n;i++)f[i]=i-(lower_bound(a+1,a+n+1,a[i]-k)-a)+1;//以第i个点为左端点
for(int i=n;i;i--)p[i]=upper_bound(a+1,a+n+1,a[i]+k)-a-i;//以第i个点为右端点
for(int i=1;i<=n;i++)g[i]=max(g[i-1],f[i]);
for(int i=n;i;i--)::k[i]=max(::k[i+1],p[i]);
int ans=0;
for(int i=1;i<=n+1;i++)ans=max(ans,g[i-1]+::k[i]);
cout<<ans<<endl;
return 0;
}
```