前缀和（P2697 宝石串）

前言

每次做出来什么本来做不出的题目，就忍不住记录一下。不过大多时候隔几天来看，就发现，啊，我当时只是做了一道这么弱智的题目呀，哈哈。前缀和确实不算太难。。

传送门

题目大意：

给你一个字符串只含G和R，求一个最长子串长度，使得两个字符的长度相等。（给的字符串长小于1e6）

如：GRGGRG

答案是：4。

思路

题目中字符串很长，暴力枚举显然不可能。

但我们仔细一看，发现不过只有两个字符G和H。我们令G为1，令R为-1，那么GR的值就为0，这显然是一个可行的子串。

那再看GRGGRG,我们开一个a数组记录前i个字符的值，那么

a[0]=0,a[1]=1,a[2]=0,a[3]=1.a[4]=2,a[5]=1,a[6]=2。

观察可得1~3是一个可行的子串（不包括1）

1~5同样可行（不包括1）

也就是说，当他们对应的a数组值相等时，中间的串必定可行，因为中间的串没有引起值的变化，那么G和R相等。

那接下来我们该怎么做呢？

我们可以用2个for循环枚举数组a，找出值相等并且下标相差最大的两个点即为最大子串，但这样复杂度过高。

O(n)做法

我们以DP的角度考虑一个优解，使得这个过程能在线性时间内完成。如对于可行的长度为2的子串，我们只需要记录出现最早的长度为2的下标和出现最晚的下标即可。这里结合代码理解：

for(int i=0;i<str1.length();i++)

	{

		if(str1[i]=='G')

			a[i+1]=a[i]+1;//计算a数组的值

		else

			a[i+1]=a[i]-1;

		dp[a[i+1][1]=min(dp[a[i+1]][1],i+1);//记录最早

		dp[a[i+1]][2]=max(dp[a[i+1]][2],i+1);//记录最晚

	}

但是新的问题又来了,a[i+1]可能是负数，数组可没有负数的下标！其实这并不难，我们把dp的第一维扩大一倍，把中间的下标当作原来的下标零来使用，像这样：

//maxn=10000007

for(int i=0;i<str1.length();i++)

	{

		if(str1[i]=='G')

			a[i+1]=a[i]+1;

		else

			a[i+1]=a[i]-1;

		dp[a[i+1]+maxn+1][1]=min(dp[a[i+1]+maxn+1][1],i+1);

		dp[a[i+1]+maxn+1][2]=max(dp[a[i+1]+maxn+1][2],i+1);

	}

完整代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn=1000009;

int a[2*maxn];

string str1;

int dp[maxn*2+9][3];

int main()

{

	cin>>str1;

	for(int i=0;i<=maxn*2-5;i++)

		dp[i][1]=100000000;//为min作预处理

	dp[maxn+1][1]=0;//这里可以把maxn+1看作原来的下标0

	for(int i=0;i<str1.length();i++)

	{

		if(str1[i]=='G')

			a[i+1]=a[i]+1;

		else

			a[i+1]=a[i]-1;

		dp[a[i+1]+maxn+1][1]=min(dp[a[i+1]+maxn+1][1],i+1);

		dp[a[i+1]+maxn+1][2]=max(dp[a[i+1]+maxn+1][2],i+1);

	}

	int sumn=0;

	for(int i=0;i<=maxn+str1.length();i++)//注意，从下标0开始

		sumn=max(sumn,dp[i][2]-dp[i][1]);

	cout<<sumn;

}

感谢dalao过目！

巴特西

前缀和（P2697 宝石串）

最新文章

热门文章