codeforce 462DIV2 C题

62 阅读 0 评论 41 点赞

我是靠谱客的博主虚心画笔，最近开发中收集的这篇文章主要介绍codeforce 462DIV2 C题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

给出一个只含有1和2的序列，有n个元素，可以选择一段区间进行翻转操作，求再反转后的最大非递减子序列的长度

分析

太菜了只想出了N^2的做法。
序列只有1和2，那么每个非递减子序列都会有一个分界点，在分界点前是1以后是2。观察可以发现，只有当翻转的区间包含这个分界点的时候，这个分界点的非递减子序列的长度才会发生变化。定义dp[i][j]为反转区间i,j，且分界点在区间i,j的最长非递减子序列的长度。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 using namespace std;
 6 const int maxn=2000+50;
 7 int n;
 8 int a[maxn];
 9 int sum1[maxn],sum2[maxn];
10 int dp[maxn][maxn];
11 int main(){
12
scanf("%d",&n);
13
sum1[0]=sum1[0]=0;
14
for(int i=1;i<=n;i++){
15
scanf("%d",&a[i]);
16
if(a[i]==1){sum1[i]=sum1[i-1]+1;sum2[i]=sum2[i-1];}
17
if(a[i]==2){sum2[i]=sum2[i-1]+1;sum1[i]=sum1[i-1];}
18 
}
19
int ans=0;
20
for(int i=0;i<=n;i++)ans=max(ans,sum1[i]+sum2[n]-sum2[i]);
21
for(int i=1;i<=n;i++)
22
dp[i][i]=sum1[i]+sum2[n]-sum2[i];
23
for(int len=2;len<=n;len++){
24
for(int i=1;i<=n-len+1;i++){
25
int j=i+len-1;
26
if(a[j]==2&&a[i]==1){
27
if(len>2)dp[i][j]=dp[i+1][j-1]-2;
28
else if(len<=2)dp[i][j]=dp[i][j-1]-2;
29 
}
30
else if(a[j]==1&&a[i]==2){
31
if(len>2)dp[i][j]=dp[i+1][j-1]+2;
32
else if(len<=2)dp[i][j]=dp[i][j-1]+2;
33 
}
34
else if(a[i]==a[j]){
35
if(len<=2)dp[i][j]=dp[i][j-1];
36
else
37
dp[i][j]=dp[i+1][j-1];
38 
}
39
dp[i][j]=max(dp[i][j],max(sum1[j]+sum2[n]-sum2[j],sum1[i-1]+sum2[n]-sum2[i-1]+(a[j]==1)));
40 
}
41 
}
42
for(int i=1;i<=n;i++){
43
for(int j=i;j<=n;j++){
44
// cout<<i<<"---->"<<j<<" "<<dp[i][j]<<endl;
45
ans=max(ans,dp[i][j]);
46 
}
47 
}
48
printf("%d",ans);
49 return 0;
50 }