CodeForces 933A A Twisty Movement 前缀和

421人浏览 / 1人评论

题目链接

  • A Twisty Movement
    • 这一题最后十秒过题,很惊险刺激,但是它留给我的思考却是没有停止的。
    • 看数据范围,必须在O(n²)之内的时间完成,否则超时。
    • 很容易想到枚举一个区间的左右端点[L, R],然后将此区间反转,可是翻转之后如何统计答案又是一个O(n)问题。
    • 为什么统计答案是O(n)问题呢?因为只有1和2两种状态,我们只要预处理出一个序列的1数量的前缀和与2数量的后缀和,然后从头到尾枚举1->2的转折点位置统计答案即可。
    • 可是O(n³)复杂度不能过题,必须另辟蹊径。
    • 更换枚举顺序,先枚举1->2的转折点位置尝试思考。
    • 枚举转折点(即为pos)后,下面就是如何确定翻转区间的问题。显然,如果翻转区间右端点R≤mid或做短点L>mid,那么区间翻转并不会改变区间内1的数量或2的数量,所以对答案不会有改变。
    • 所以反转的区间必须满足L≤pos<R,我们以pos为轴进行翻转,便于统计答案。
    • 统计答案的方法:算出[1, L-1]中1的个数,加上[L, pos]中2的个数,加上[pos+1, R]中1的个数,再加上[R+1, n]中2的个数。
    • 我们发现,先枚举转折点再枚举区间还是需要枚举3个量(pos、L、R),复杂度似乎没有优化。
    • 发现L就是在[1, pos]这个区间中取一个最优值,R就是在[pos+1, n]这个区间中取一个最优值,两者之间相互独立、互不相关。
    • 于是我们可以平行地枚举L和R,时间复杂度降到O(n²)
    • (注意:并不一定要翻转区间,写代码时注意细节)

代码:

#include<cstdio>
#include<algorithm>
using namespace std;
int a[2010],prefix[2010],sufix[2010];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	{
		scanf("%d",&a[i]);
	}
	prefix[0]=a[0]==1;
	for(int i=1;i<n;++i)
	{
		prefix[i]=prefix[i-1]+(a[i]==1);
	}
	sufix[n-1]=a[n-1]==2;
	for(int i=n-2;i>=0;--i)
	{
		sufix[i]=sufix[i+1]+(a[i]==2);
	}
	int maxi=0;
	for(int i=0;i<=n;++i)
	{
		int max1=0;
		for(int l=0;l<=i;++l)
		{
			max1=max(max1,(l>0?prefix[l-1]:0)+sufix[l]-sufix[i]);
		}
		int max2=0;
		for(int r=i;r<=n;++r)
		{
			max2=max(max2,(r+1<n?sufix[r+1]:0)+prefix[r]-(i>0?prefix[i-1]:0));
		}
		if(max1+max2>maxi)
		{
			maxi=max1+max2;
		}
	}
	printf("%d",maxi);
	return 0;
}

全部评论