多校的时候数据太水了，竟然让我过了。
题目实际上就是求的从某个点开始到终点的非升非降序列长度和的最大值，其中要排除重复的元素，就是DP
官方解题报告
考虑题目的一个简化版本：使双端队列单调上升。对于序列A和队列Q，找出队列中最早出现的数字Ax，则Ax将Q分成的两个部分分别是原序列中以Ax开始的最长上升和最长下降序列，答案即为这两者之和的最大值。而对于本体，由于存在相同的元素，所以只要找到以Ax为起点的最长不下降序列和最长不上升序列的和，然后减去两个里面出现Ax次数的最小值即可。
我的代码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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
using namespace std;
const int maxn=100010;
int a[maxn];
int jia[maxn];
int jian[maxn];
int dp[2][maxn];
int jia_num;
int jian_num;
int erfenjia(int s,int t,int k)
{
if(s==t)
return s;
int m=(s+t)/2;
if(k>=jia[m])
return erfenjia(m+1,t,k);
else
return erfenjia(s,m,k);
}
int erfenjian(int s,int t,int k)
{
if(s==t)
return s;
int m=(s+t)/2;
if(k<=jian[m])
return erfenjian(m+1,t,k);
else
return erfenjian(s,m,k);
}
int erfen(int*a ,int s,int t,int k,bool x)
{
if(s==t)
return s;
int m=(s+t)/2+1;
if(x==0&&k<=a[m])
return erfen(a,s,m-1,k,x);
else if(x==1&&k>=a[m])
return erfen(a,s,m-1,k,x);
else
return erfen(a,m,t,k,x);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
int i,j;
int ans=1;
scanf("%d",&n);
zero(jia);
zero(jian);
jia_num=jian_num=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
int tmp=a[n-i-1];
if(i!=0)
{
int s,t;
if(tmp>=jia[jia_num-1])
s=jia_num++;
else
s=erfenjia(0,jia_num-1,tmp);
if(tmp<=jian[jian_num-1])
t=jian_num++;
else
t=erfenjian(0,jian_num-1,tmp);
jia[s]=tmp;
jian[t]=tmp;
int sx=erfen(jia,0,jia_num-1,tmp,0);
int sy=erfen(jian,0,jian_num-1,tmp,1);
if(sx==0&&jia[sx]<=tmp)
sx=-1;
if(sy==0&&jian[sy]>=tmp)
sy=-1;
int com=s+1+t+1-min(s-sx,t-sy);
// cout<<min(s-sx,t-sy)<<endl;
// cout<<s<<' '<<t<<endl;
// cout<<sx<<' '<<sy<<endl;
if(com>ans)
ans=com;
}
else
{
jia[jia_num++]=tmp;
jian[jian_num++]=tmp;
}
}
printf("%d\n",ans);
}
return 0;
}
标程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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using namespace std;
const int N = 100010;
int a[N];
int num_up[N],num_down[N];
int dp_up[N],dp_down[N];
int n;
void getdp(int dp[],int num[])
{
dp[n]=1;
vector<int> v;
v.push_back(a[n]);
vector<int>::iterator iter;
for(int i=n-1;i>=1;i--){
int sz=v.size();
if(a[i]>v[sz-1]){
v.push_back(a[i]);
dp[i]=sz+1;
num[i]=1;
}else if(a[i]==v[sz-1]){
iter=upper_bound(v.begin(),v.end(),a[i]);
dp[i]=iter-v.begin()+1;
v.push_back(a[i]);
pair<vector<int>::iterator,vector<int>::iterator> bounds;
bounds=equal_range(v.begin(),v.end(),a[i]);
num[i]=bounds.second-bounds.first;
}else{
iter=upper_bound(v.begin(),v.end(),a[i]);
dp[i]=iter-v.begin()+1;
*iter=a[i];
pair<vector<int>::iterator,vector<int>::iterator> bounds;
bounds=equal_range(v.begin(),v.end(),a[i]);
num[i]=bounds.second-bounds.first;
}
}
}
void debug(int a[])
{
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
printf("\n");
}
int main(void)
{
int T;
scanf("%d",&T);
while(T--){
int ans=0;
scanf("%d",&n);
map<int,int> mp;
mp.clear();
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
getdp(dp_up,num_up);
for(int i=1;i<=n;i++){
a[i]=-a[i];
}
getdp(dp_down,num_down);
for(int i=1;i<=n;i++){
mp[a[i]]++;
ans=max(ans,dp_down[i]+dp_up[i]-min(num_up[i],num_down[i]));
}
printf("%d\n",ans);
}
return 0;
}