Codeforces Round #462 (Div. 1) A. A Twisty Movement (LIS+思维)

标签: 思维

题目链接
在这里插入图片描述
题意:你可以任意选择一个区间,将该区间的数进行反转,求反转后最长的LIS。
思路:dp1【i】【j】代表区间【i,j】的LIS长度,dp2【i】【j】是区间【i,j】反转后的LIS,一个区间反转后对整个答案的贡献就是dp1【1】【n】-dp1【i】【j】+dp2【i】【j】,由于n小于2000,大胆暴力就可以了。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int maxn=2e3+1;
int n,dp1[maxn][maxn],dp2[maxn][maxn],a[maxn],ans=0;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)
	{
		int cnt1=0,cnt2=0;
		for(int j=i;j<=n;++j)
		{
			if(a[j]==1) cnt1++;
		else cnt2=max(cnt2,cnt1)+1;
		dp1[i][j]=max(cnt1,cnt2);
		}
		cnt1=cnt2=0;
		for(int j=i;j<=n;++j)
		{
			if(a[j]==2) cnt1++;
		else cnt2=max(cnt2,cnt1)+1;
		dp2[i][j]=max(cnt1,cnt2);
		}
	}
	for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
	ans=max(ans,dp1[1][n]-dp1[i][j]+dp2[i][j]);
	printf("%d\n",ans);
}
版权声明:本文为qq_42479630原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42479630/article/details/105299547