题意

test20181007 wzoi

分析

考场40分

错误的Manacher+dp。

用\(f(i)\)表示\(s_{1 \sim i}\)的最长偶数回文覆盖长度，在Manacher的同时用刷表法转移，每次还要对\(f(i-1)\)取\(\max\)。

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const int MAXN=1e6+7;

int n;

char s[MAXN];

char s_new[MAXN<<1];

int p[MAXN<<1];

int Init()

{

	int len=strlen(s);

	s_new[0]='$';

	s_new[1]='#';

	int j=2;

	for(int i=0;i<len;++i)

	{

		s_new[j++]=s[i];

		s_new[j++]='#';

	}

	s_new[j]=0;

	return j;

}

int f[MAXN];

void Manacher()

{

	int len=Init();

	int id,mx=0;

	for(int i=1;i<len;++i)

	{

		if(i<mx)

			p[i]=min(p[2*id-i],mx-i);

		else

			p[i]=1;

		while(s_new[i-p[i]]==s_new[i+p[i]])

			++p[i];

		if(mx<i+p[i])

		{

			id=i;

			mx=i+p[i];

		}

		if(i>1&&s_new[i]=='#')

		{

			f[i/2]=max(f[i/2],f[i/2-1]);

			f[i/2+(p[i]-1)/2]=max(f[i/2+(p[i]-1)/2],f[i/2-(p[i]-1)/2]+p[i]-1);

		}

	}

}

/*

0011011110

*/

int main()

{

//  freopen("wzoi.in","r",stdin);

//  freopen("wzoi.out","w",stdout);

	scanf("%s",s);

	n=strlen(s);

	Manacher();

	printf("%d\n",f[n]/2*10+(n-f[n])/2*5);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

然而考虑这组数据：

0011011110

\(f\)算出来：

0,2,2,2,4,4,6,6,8,8

更新没有覆盖整个偶数回文区间，导致出错。

要改的话要区间复杂的操作，无论是否有数据结构可行时间都不允许了。

好歹还有40分。

标解

test20181007 wzoi

单调栈+贪心解决问题。

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

int main()

{

  freopen("wzoi.in","r",stdin);

  freopen("wzoi.out","w",stdout);

	string a,b;

	cin>>a;

	for(auto c:a)

	{

		if(b.empty()||b.back()!=c)

			b.push_back(c);

		else

			b.pop_back();

	}

	printf("%d\n",5*(a.size()-b.size()/2));

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}