poj1741，【dp】POJ-2817

突然發現狀態狀態Dp很難上手啊

這個題目的數據量不是特別多

可以用全排列的方式來計算（不過略顯麻煩）

然后看別人的解題報告

自己總結下狀態壓縮dp的大致思想

用一個state來表示各組數據運用的情況

state用2進制位來表示

1和0分別代表所在的位的那組數據是否使用

這個里面牽扯到了很多的位運算

用&并運算來 和~(1<<i) 操作就是置i位為0

?

?

#include <stdio.h>

#include <string.h>

#include <math.h>

?

char word[11][15];

int mm[11][11];

int len[11];

int n;

int dp[2000][11];

?

void cal(int a , int b)

{

?

? ? ?int i , j , result , max = 0;

? ? ?for ( ?i = 0; i < len[a]; ++i )

? ? ?{

? ? ? ? result = 0;

? ? ? ? for ( ?j = 0; j < len[b]; ++j )

? ? ? ? {

? ? ? ? ? ? if ( i+j<len[a] && word[a][i+j] == word[b][j] ) ++result;

? ? ? ? }

? ? ? ? max = max>result?max:result;

? ? ?}

? ? ?for ( ?i = 1; i < len[b]; ++i )

? ? ?{

? ? ? ? result = 0;

? ? ? ? for ( ?j = 0; j < len[a]; ++j )

? ? ? ? {

? ? ? ? ? ? if ( i+j<len[b] && word[b][i+j] == word[a][j] ) ++result;

? ? ? ? }

? ? ? ? max = max>result?max:result;

? ? ?}

?

? ? ?mm[a][b] = mm[b][a] = max;

?

}

?

int fun_dp(int state , int last)

//第一個參數state表示狀態，也就是各個單詞的取用情況，是用二進制的位運算解決的。因為每個單詞只有兩種狀態，被用了和沒被用，那我們就用1表示取了這個單詞，0表示沒取。每一位表示一個單詞的取用情況,第i位表示第i-1個單詞是否被取。poj1741。比如10011表示word[5]word[2]word[1]被取，而word[4]word[3]未被取。

{

? ? int state_t = state , i , result , tmp , max = 0;

? ? state_t &= (~(1<<(last-1)));

//state_t是state去掉last的狀態。

?

? ? if(state_t == 0)

//如果state去掉last以后是0，也就是說，前面一個單詞都沒取，那last就是第一個單詞，沒有和它相鄰的單詞，返回0

? ? ? ? return 0;

?

? ? if(dp[state][last])

? ? ? ? return dp[state][last];

?

? ? for( i = 0 ; i < n ; ++i )

? ? {

? ? ? ? result = 0;

? ? ? ? tmp = state_t & (~(1<<i));

? ? ? ? if( tmp != state_t )

? ? ? ? ? ? result = fun_dp(state_t,i+1) + mm[i+1][last];

//如果state_t的i這位是1，也就是說，state_t包括word[i+1],那么遞歸調用Fun函數得到state_t包括的所有單詞都作為末一行的最大公共字母數，此時word[i+1]作為word[last]的相鄰行，所以再加上mm[i+1][last]，取最大值存起來就可以了

? ? ? ? max = max>result?max:result;

? ? }

?

? ? dp[state][last] = max;

?

? ? return max;

}

?

int main()

{

? ? int i , j , power , max , temp;

?

? ? while(scanf("%d",&n) && n > 0)

? ? {

? ? ? ? max = 0;

?

? ? ? ? memset(dp,0,sizeof(dp));

?

? ? ? ? for( i = 1 ; i <= n ; i++ )

? ? ? ? {

? ? ? ? ? ? scanf("%s",word[i]);

? ? ? ? ? ? len[i] = strlen(word[i]);

? ? ? ? }

?

? ? ? ? for( i = 1 ; i <= n ; i++ )

? ? ? ? ? ? for( j = i+1 ; j <= n ; j++ )

? ? ? ? ? ? {

? ? ? ? ? ? ? ? cal(i,j);

? ? ? ? ? ? }

? ? ? ? power = (int)pow(2,n);

?

? ? ? ? for( i = 1 ; i <= n ; i++ )

? ? ? ? {

? ? ? ? ? ? temp = fun_dp(power-1,i);

? ? ? ? ? ? max = max>temp?max:temp;

? ? ? ? }

? ? // ? ?for( i = 1 ; i <= n ; i++ ) ? ? 調試程序用的

? ? ?// ? ? ? for( j = 1 ; j <= n ; j++ )

? ? ?// ? ? ? ? ? printf("%d ?",mm[i][j]);

? ? ? ? printf("%d\n",max);

? ? }

? ? return 0;

}