题目意思： 给长度为n（n<=2000）的数字串，数字只能为1或者2，可以将其中一段区间[l,r]翻转，求翻转后的最长非递减子序列长度。
第一种：先预处理1的前缀和，以及2的后缀和，每次枚举翻转区间，则答案为左区间的1的前缀和
+枚举区间内最长非递增子序列的长度+右区间2的后缀和数目。
先固定左端点l，然后枚举右端点，碰到1要统计，碰到2要更新值，假如使用此处的2，
则之前区间内的1无法继续使用。复杂度为n^2
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int pre1[2010],suf2[2010];
int a[2010];
int main()
{
int n;
cin>>n;
pre1[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
pre1[i]=pre1[i-1];
if(a[i]==1)
pre1[i]++;
}
suf2[n+1]=0;
for(int i=n;i>=1;i--)
{
suf2[i]=suf2[i+1];
if(a[i]==2)
suf2[i]++;
}
int ans=0;
/* for(int i=1;i<=n;i++)
{
ans=max(ans,pre1[i]+suf2[i]);
}*/
for(int l=1;l<=n;l++)
{
int t1=pre1[l-1];
int tt1=0,tt2=0;
for(int r=l;r<=n;r++)
{
int t2=suf2[r+1];
if(a[r]==1)
tt1++;//l-r的最优值
else
{
tt2++;
tt1=max(tt1,tt2);//如果2出现，要先更新最优值，就是2的数目
}
ans=max(ans,t1+t2+tt1);
}
}
cout<<ans<<endl;
return 0;
}
第二中方法，采用dp思想，每一个最优答案可视为1串+...+2串+..+1串+..+2串..的组合，则
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int pre1[2010],suf2[2010];
int a[2010];
int dp[2010][2010][3];
int main()
{
int t1=0,t2=0,t3=0,t4=0;
int n,x;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
if(x==1)
{
t1++;
t3=max(t3,t2)+1;
}
else
{
t2=max(t2,t1)+1;
t4=max(t3,t4)+1;
}
}
cout<<max(t3,t4)<<endl;
return 0;
}
时间复杂度为n
做这种题还是要多动笔，分类找规律，列方程，优化
转载请注明原文地址: https://www.6miu.com/read-2626972.html
