題目給幾個字符串，可以給它們添加前導空格，然后排列，計算每一個字符串和前一個字符串相同非空格字符相等的個數，求可能的最大個數。

狀態DP：

d[S][i][j]表示已經用的字符串集合S且排列的最后一個是前面帶j個空格的字符串i

轉移就枚舉從什么字符串幾個前導0結尾轉移過來的。還可以預處理一下各個情況的字符串相同字符個數。時間復雜度大概就O(n²*100+2ⁿ*n²*100)。

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 int d[1<<10][10][10],val[10][10][10][10]; 6 char str[11][11]; 7 int main(){ 8 int n; 9 while(~scanf("%d",&n) && n){ 10 memset(str,0,sizeof(str)); 11 for(int i=0; i<n; ++i){ 12 scanf("%s",str[i]); 13 } 14 memset(val,0,sizeof(val)); 15 for(int i=0; i<n; ++i){ 16 for(int j=0; j<n; ++j){ 17 if(i==j) continue; 18 for(int x=0; x<10; ++x){ 19 for(int y=0; y<10; ++y){ 20 for(int k=max(x,y); str[i][k-x]&&str[j][k-y]; ++k){ 21 if(str[i][k-x]==str[j][k-y]) ++val[i][j][x][y]; 22 } 23 } 24 } 25 } 26 } 27 memset(d,0,sizeof(d)); 28 for(int s=1; s<(1<<n); ++s){ 29 for(int i=0; i<n; ++i){ 30 if(((s>>i)&1)==0) continue; 31 for(int j=0; j<10; ++j){ 32 for(int x=0; x<n; ++x){ 33 if(x==i || ((s>>x)&1)==0) continue; 34 for(int y=0; y<10; ++y){ 35 d[s][i][j]=max(d[s][i][j],d[s^(1<<i)][x][y]+val[i][x][j][y]); 36 } 37 } 38 } 39 } 40 } 41 int res=0; 42 for(int i=0; i<n; ++i){ 43 for(int j=0; j<10; ++j) res=max(res,d[(1<<n)-1][i][j]); 44 } 45 printf("%d\n",res); 46 } 47 return 0; 48 }

?

轉載于:https://www.cnblogs.com/WABoss/p/5191002.html

總結

以上是生活随笔為你收集整理的POJ2817 WordStack（状压DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。