2013暑期多校联合训练\第三场\Problem H

灰太狼 2021-12-02 01:36 215阅读 0赞

虽然题解说是简单题，但是本弱菜还是花了很长时间才订正好。咨询了一位大神，在此先表示感谢。

题解说的O（3^N）的方法没学会，现在有种O（2^N\*M），M为回文序列总数。

进入正题，先是状态压缩，因为数据范围很小啦~ 把所有回文串的状态记录下来。下面开始DP，f\[i\]表示i拆成2进制以后，位置上为1的所表示的字符串，都删掉需要多少步。可以这么理解，是回文串的肯定只要1步，如果当前这个状态的字符串，可以加上一个回文串，就要加上一步，看看是否能够更优。f\[i|x\](i和x的二进制数没有相同位置的1)和f\[i\]+1比较，若优，则更新。

Tip：在做这题的过程中，学到了两点小知识。

A&B==0 可以判断是否有相同位置的0，A|B可以将没有相同位置1的两个数相加。

#include <iostream>
    using namespace std;
    
    int i,j,k,t,n,flag,l,a[17],x[70000],xx,T,f[70000],b[17];
    char ss[17],s[17];
    
    int min(int x,int y)
    {
    	if (x<y) return x;
    	return y;
    }
    
    void prechange()
    {
    	l=strlen(s);
    	xx=0;
    	n=1;
    	for (i=1;i<=l;i++)	n=n*2;
    	for (i=1;i<=n-1;i++)
    	{
    		k=i;
    		t=1;
    		memset(a,0,sizeof(a));
    		while (k!=0)
    		{
    			a[t]=k%2;k=k/2;t++;
    		}
    		t=1;
    		for (j=1;j<=l;j++)
    			if (a[j]==1)
    			{
    				ss[t]=s[j-1];
    				t++;
    			}
    		flag=0;
    		t--;
    		for (j=1;j<=t/2;j++)
    			if (ss[j]!=ss[t-j+1])
    			{
    				flag=1;
    				break;
    			}
    		if (flag==0)
    			{
    				xx++;
    				x[xx]=i;
    			}
    		}
    }
    
    int main()
    {
    	scanf("%d",&T);
    	while (T--)
    	{
    		scanf("%s",&s);
    		prechange();
    		memset(f,0x3f,sizeof(f));
    		f[0]=0;
    		for (i=0;i<n;i++)
    			for (j=1;j<=xx;j++)
    				if ((i&x[j])==0)
    					f[i|x[j]]=min(f[i|x[j]],f[i]+1);
    		printf("%d\n",f[n-1]);
    	}
    	return 0;
    }