hdu 3474 Necklace

把C看成1，J看成-1，那么问题就转化为，有多少段以i结尾，长度为N，且任意i-n+1<=j<=i，sum[i]-sum[j]>=0的区间，由于任意，这n个式子中的最小值也必须满足大于等于0的条件，那么，我们可以对每个i维护一个长度为n的区间内的最大值k，用sum[i]-k来表示sum[i]-max{sum[j]},即min{sum[i]-sum[j]},跟hdu 3415一样的做法

代码:

#include<iostream>
#include<memory.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<ctime>
using namespace std;
const int MAX=2000005;
int sum[MAX],pos[MAX],id[MAX],a[MAX],cnt,n,N;
bool ok[MAX];
char s[MAX];
void solve(int k)
{
int i,head=0,tail=0;
pos[0]=0; id[0]=0;
for(i=1;i<=N;i++)
{
while(head<=tail&&i-id[head]>n)
head++;
if(i>n&&sum[i]-pos[head]>=0)
{
if(k)
{
if(n+n-i)
ok[n+n-i]=true;
else
ok[n]=true;
}
else
ok[i-n]=true;
}
while(head<=tail&&pos[tail]<=sum[i])
tail--;
pos[++tail]=sum[i];
id[tail]=i;
}
}
int main()
{
int i,j,k,T,ca;
scanf("%d",&T);
for(ca=1;ca<=T;ca++)
{
scanf("%s",s);
n=strlen(s);
sum[0]=0;
for(i=0;i<n;i++)
{
if(s[i]=='C')
a[i+1]=a[i+1+n]=1;
else
a[i+1]=a[i+1+n]=-1;
}
N=2*n;
for(i=1;i<=N;i++)
{
sum[i]=sum[i-1]+a[i];
}
cnt=0;
memset(ok,false,sizeof(ok));
solve(0);
for(i=1;i<=N;i++)
sum[i]=sum[i-1]+a[N-i+1];
solve(1);
for(i=1;i<=N;i++)
if(ok[i])
cnt++;
printf("Case %d: %dn",ca,cnt);
}
return 0;
}

最后

以上就是危机苗条为你收集整理的hdu 3474 Necklace的全部内容，希望文章能够帮你解决hdu 3474 Necklace所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。