[DP] Codeforces 930C. Teodor is not a liar!

题面意思是在保证不发现问题的情况下询问最多的点。

考虑不发现问题是怎样的情况,应该是个单峰的,所以只要求以最长的单峰子序列即可。

正反刷两趟 \(DP\) ,树状数组优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,m,a[maxn],f1[maxn],f2[maxn],bit[maxn],ans;
void Update(int x,int y){
for(;x<=n;x+=(x&(-x))) bit[x]=max(bit[x],y);
}
int Query(int x){
int res=0;
for(;x;x-=(x&(-x))) res=max(res,bit[x]);
return res;
}
int main(){
freopen("cf930C.in","r",stdin);
freopen("cf930C.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x,y; scanf("%d%d",&x,&y);
a[x]++; a[y+1]--;
}
for(int i=2;i<=m;i++) a[i]+=a[i-1];
for(int i=1;i<=m;i++) f1[i]=Query(a[i]+1)+1, Update(a[i]+1,f1[i]);
memset(bit,0,sizeof(bit));
for(int i=m;i>=1;i--) f2[i]=Query(a[i]+1)+1, Update(a[i]+1,f2[i]);
for(int i=1;i<=m;i++) ans=max(ans,f1[i]+f2[i]-1);
printf("%d\n",ans);
return 0;
}