题意：

　 输入正整数n和k（1<=n<=400,1<=k<=10），求长度为n的01串中有多少个不含长度至少为k的回文连续子串。例如，n=k=3时只有4个串满足条件：001，011，100，110。

 

分析：

　　做这题的时候走了很多弯路，自以为想到了一个不用表示状态的dp，然而在保证不回文的时候就发现了很多问题。其实本题k的规模很小，所以应该要想到状压的。一个串中只要保证不含长度为k也不含长度为k+1的回文串，那么就不会出现大于k的回文串，所以我们构造的时候只要保证前面两个条件符合即可。

　　状压记录后k的字符串，填新字符时保证不会构造出长度为k或k+1的回文串即可。

 

代码如下：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define Maxn 410 8 #define Maxd 3010 9 #define Mod  100000000710 11 int f[Maxn][Maxd];12 13 bool check(int x,int kl)14 {15     int sl=1<
           
            >=1;21 }22 return 1;23 }24 25 int main()26 {27 int T;28 scanf("%d",&T);29 while(T--)30 {31 int n,k;32 scanf("%d%d",&n,&k);33 if(k==1) {printf("0\n");continue;}34 memset(f,0,sizeof(f));35 f[0][0]=1;36 int ans=0;37 for(int i=1;i<=n;i++)38 {39 for(int j=0;j<=(1<
            
             k&&check(j&((1<
             
              =k&&check(j&((1<
             
            
           
          
         
        
       
      

这题没有特判k=1的情况导致WA了很久，可能是我的代码风格太渣的问题TAT。

 

2016-03-04 13:25:02