HDU4628+状态压缩DP

  1 /*
  2 状态压缩DP
  3 dp[ i ]:达到i状态的最小step。
  4 题意：每次可以去掉一个回文串，求最少几步能取完。
  5 */
  6 #include<stdio.h>
  7 #include<string.h>
  8 #include<stdlib.h>
  9 #include<algorithm>
 10 #include<iostream>
 11 #include<queue>
 12 #include<map>
 13 #include<math.h>
 14 using namespace std;
 15 typedef long long ll;
 16 //typedef __int64 int64;
 17 const int maxn = 18;
 18 const int inf = 0x3f3f3f3f;
 19 const double pi=acos(-1.0);
 20 const double eps = 1e-8;
 21 int dp[ 1<<maxn ];
 22 char s[ maxn ];
 23 int state[ 1<<maxn ];//回文的状态
 24 
 25 bool JudgeOneZero( int ss,int len ){
 26     int Index[ maxn ];
 27     int cc = 0;
 28     int IndexOfString = 0;
 29     while( IndexOfString<len ){
 30         if( ss%2==1 ){// 所有的 “1” 代表该位置上有字母，即这些组合是回文串
 31             Index[ cc++ ] = IndexOfString;
 32         }
 33         ss /= 2;
 34         IndexOfString++;
 35     }
 36     if( cc==1 ) return true;
 37     int L,R;
 38     L = 0;
 39     R = cc-1;
 40     while( L<=R ){
 41         if( s[Index[L]]!=s[Index[R]] ) return false;
 42         L++;
 43         R--;
 44     }
 45     return true;
 46 }//判断s是否是回文状态 
 47 
 48 int init_state( int len ){
 49     int cnt = 0;
 50     int N = 1<<len;
 51     state[ cnt++ ] = 0;
 52     for( int i=1;i<N;i++ ){
 53         if( JudgeOneZero( i,len )==true ){
 54             state[ cnt++ ] = i;
 55         }
 56     }
 57     return cnt;
 58 } //初始化回文的状态
 59 
 60 bool Judge( int cur,int nxt,int len ){//当前状态cur，前一状态nxt
 61     int Index[ maxn ];
 62     int cc = 0;
 63     int IndexOfString = 0;
 64     while( IndexOfString<len ){
 65         if( cur%2==1 ){
 66             if( nxt%2==0 ) return false;
 67         }//当前状态为1，前一状态必须为1
 68         if( nxt%2==0 ){
 69             if( cur%2==1 ) return false;
 70         }//前一状态是0，当前状态也必须是0
 71         if( cur%2==0&&nxt%2==1 ){
 72             Index[ cc++ ] = IndexOfString;
 73         }
 74         IndexOfString++; 
 75         cur /= 2;
 76         nxt /= 2;
 77     }
 78     if( cc==1 ) return true;
 79     int L,R;
 80     L = 0;
 81     R = cc-1;
 82     //printf("cc=%d
",cc);
 83     while( L<=R ){
 84         if( s[Index[L]]!=s[Index[R]] ) return false;
 85         L++;
 86         R--;
 87     }
 88     return true;
 89 }
 90 
 91 int main(){
 92     int T;
 93     scanf("%d",&T);
 94     while( T-- ){
 95         scanf("%s",s);
 96         int n = strlen(s);
 97         int cnt = init_state( n );
 98         int N = (1<<n);
 99         for( int i=0;i<N;i++ )
100             dp[ i ] = inf;
101         dp[ N-1 ] = 0;
102         /*
103         for( int i=N-2;i>=0;i-- ){
104              for( int j=0;j<N;j++ ){
105                  if( i==j ) continue;
106                  if( Judge( i,j,n )==true ){
107                      //printf("i=%d, j=%d
",i,j);
108                      dp[ i ] = min( dp[i],dp[j]+1 );
109                      //printf("dp[%d] = %d

",i,dp[i]);
110                  }
111              }
112         }
113         */
114         for( int i=N-2;i>=0;i-- ){
115             for( int j=0;j<cnt;j++ ){
116                 if( 0==(i&state[j]) ){
117                     dp[ i ] = min( dp[i],dp[state[j]|i]+1 );
118                 }
119             }
120         }            
121         printf("%d
",dp[0]);
122     }
123     return 0;
124 }
View Code
keep moving...