題目給一張n×n的格子，每個格子都有數(shù)字，要從格子中取若干個數(shù)字，八個方向相鄰的數(shù)字不能一起取，問取的數(shù)字最大和是多少。

從第一行一行一行看下去，可以發(fā)現(xiàn)第1行取哪幾列只會影響到第2行，第3行后面的一點影響都沒有。即第i行的決策只受i-1行決策的影響。

那么自然想到狀態(tài)DP——

• dp[i][S]前i行其中第i行取的列的集合是S的取數(shù)最大和
• dp[i][S]=max(dp[i-1][S'])+集合S數(shù)字和（S是S'的合法的下一行的取法）

雖然題目n最多15，集合S就2¹⁵種狀態(tài)，但事實上合法的（不能同時取同一行相鄰的兩列數(shù)字）集合S狀態(tài)只有1000多個。枚舉即可轉(zhuǎn)移，為了保證時間復(fù)雜度做一些預(yù)處理就行了。

1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 using namespace std; 6 int read(char *&s){ 7 int res=-1; 8 sscanf(s,"%d",&res); 9 while(*s==' ') ++s; 10 while(*s>='0' && *s<='9') ++s; 11 while(*s==' ') ++s; 12 return res; 13 } 14 int n,a[15][15],d[15][1<<15],sta[1<<15],sn; 15 bool isok(int s){ 16 for(int i=1; i<n; ++i){ 17 if(((s>>i-1)&1) && ((s>>i)&1)) return 0; 18 } 19 return 1; 20 } 21 bool isok(int x,int y){ 22 for(int i=0; i<n; ++i){ 23 if(((x>>i)&1)==0) continue; 24 if((y>>i)&1) return 0; 25 if(i>0 && ((y>>i-1)&1)) return 0; 26 if(i<n-1 && ((y>>i+1)&1)) return 0; 27 } 28 return 1; 29 } 30 int main(){ 31 char str[1111]; 32 while(gets(str) && *str){ 33 n=0; 34 char *s=str; int t; 35 while(t=read(s),t!=-1) a[0][n++]=t; 36 for(int i=1; i<n; ++i){ 37 gets(str); s=str; 38 for(int j=0; j<n; ++j) a[i][j]=read(s); 39 } 40 sn=0; 41 for(int i=0; i<(1<<n); ++i){ 42 if(isok(i)) sta[sn++]=i; 43 } 44 memset(d,0,sizeof(d)); 45 for(int i=0; i<sn; ++i){ 46 for(int j=0; j<n; ++j){ 47 if((sta[i]>>j)&1) d[0][sta[i]]+=a[0][j]; 48 } 49 } 50 vector<int> vec[2222]; 51 for(int i=0; i<sn; ++i){ 52 for(int j=0; j<sn; ++j){ 53 if(isok(sta[i],sta[j])) vec[i].push_back(j); 54 } 55 } 56 for(int i=1; i<n; ++i){ 57 for(int j=0; j<sn; ++j){ 58 for(int k=0; k!=vec[j].size(); ++k) d[i][sta[j]]=max(d[i][sta[j]],d[i-1][sta[vec[j][k]]]); 59 for(int k=0; k<n; ++k){ 60 if((sta[j]>>k)&1) d[i][sta[j]]+=a[i][k]; 61 } 62 } 63 } 64 int res=0; 65 for(int i=0; i<sn; ++i){ 66 res=max(res,d[n-1][sta[i]]); 67 } 68 printf("%d\n",res); 69 getchar(); 70 } 71 return 0; 72 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/WABoss/p/5188403.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。