奉上大佬博客 https://blog.csdn.net/accry/article/details/6607703
動態(tài)規(guī)劃本來就很抽象，狀態(tài)的設(shè)定和狀態(tài)的轉(zhuǎn)移都不好把握，而狀態(tài)壓縮的動態(tài)規(guī)劃解決的就是那種狀態(tài)很多，不容易用一般的方法表示的動態(tài)規(guī)劃問題，這個就更加的難于把握了。難點在于以下幾個方面：狀態(tài)怎么壓縮？壓縮后怎么表示？怎么轉(zhuǎn)移？是否具有最優(yōu)子結(jié)構(gòu)？是否滿足后效性？涉及到一些位運算的操作，雖然比較抽象，但本質(zhì)還是動態(tài)規(guī)劃。找準(zhǔn)動態(tài)規(guī)劃幾個方面的問題，深刻理解動態(tài)規(guī)劃的原理，開動腦筋思考問題。這才是掌握動態(tài)規(guī)劃的關(guān)鍵。

動態(tài)規(guī)劃最關(guān)鍵的要處理的問題就是位運算的操作，容易出錯，狀態(tài)的設(shè)計也直接決定了程序的效率，或者代碼長短。狀態(tài)轉(zhuǎn)移方程一定要仔細推敲，不可一帶而過，要思考為什么這么做，掌握一個套路，遇見這類問題能快速的識別出問題的本質(zhì)，找出狀態(tài)轉(zhuǎn)移方程和DP的邊界條件。

下面是一些關(guān)于狀態(tài)壓縮DP的題目，大都不難。狀壓DP的東西還有很多，還會接著總結(jié)。

【POJ3254】Corn Fields

【題目大意】一個矩陣?yán)镉泻芏喔褡?#xff0c;每個格子有兩種狀態(tài)，可以放牧和不可以放牧，可以放牧用1表示，否則用0表示，在這塊牧場放牛，要求兩個相鄰的方格不能同時放牛，即牛與牛不能相鄰。問有多少種放牛方案(一頭牛都不放也是一種方案)

【解析】根據(jù)題意，把每一行的狀態(tài)用二進制的數(shù)表示，0代表不在這塊放牛，1表示在這一塊放牛。首先很容易看到，每一行的狀態(tài)要符合牧場的硬件條件，即牛必須放在能放牧的方格上。這樣就能排除一些狀態(tài)。另外，牛與牛之間不能相鄰，這樣就要求每一行中不能存在兩個相鄰的1，這樣也能排除很多狀態(tài)。然后就是根據(jù)上一行的狀態(tài)轉(zhuǎn)移到當(dāng)前行的狀態(tài)的問題了。必須符合不能有兩個1在同一列（兩只牛也不能豎著相鄰）的條件。這樣也能去掉一些狀態(tài)。然后，上一行的所有符合條件的狀態(tài)的總的方案數(shù)就是當(dāng)前行該狀態(tài)的方案數(shù)。

【狀態(tài)表示】dp[state][i]：在狀態(tài)為state時，到第i行符合條件的可以放牛的方案數(shù)

【狀態(tài)轉(zhuǎn)移方程】dp[state][i] =Sigma dp[state’][i-1] （state’為符合條件的所有狀態(tài)）

【DP邊界條件】首行放牛的方案數(shù)dp[state][1] =1(state符合條件) OR 0 (state不符合條件)

【代碼】

#include <cstdio> #include <cstring> using namespace std; #define mod 100000000 int M,N,top = 0; int state[600],num[110]; int dp[20][600]; int cur[20]; inline bool ok(int x){if(x&x<<1)return 0;return 1; } void init(){top = 0;int total = 1 << N;for(int i = 0; i < total; ++i){if(ok(i))state[++top] = i;} } inline bool fit(int x,int k){if(x&cur[k])return 0;return 1; } inline int jcount(int x) {int cnt=0;while(x){cnt++;x&=(x-1);}return cnt; }int main(){while(scanf("%d%d",&M,&N)!= EOF){init();memset(dp,0,sizeof(dp));for(int i = 1; i <= M; ++i){cur[i] = 0;int num;for(int j = 1; j <= N; ++j){scanf("%d",&num);if(num == 0)cur[i] +=(1<<(N-j));}}for(int i = 1;i <= top;i++){if(fit(state[i],1)){dp[1][i] = 1;}}for(int i = 2; i <= M; ++i){for(int k = 1; k <= top; ++k){if(!fit(state[k],i))continue;for(int j = 1; j <= top ;++j){if(!fit(state[j],i-1))continue;if(state[k]&state[j])continue;dp[i][k] = (dp[i][k] +dp[i-1][j])%mod;}}}int ans = 0;for(int i = 1; i <= top; ++i){ans = (ans + dp[M][i])%mod;}printf("%d\n",ans);} }

【POJ1185】炮兵陣地–經(jīng)典狀壓DP

【題目大意】類似于上面一道題，一個方格組成的矩陣，每個方格可以放大炮用0表示，不可以放大炮用1表示（原題用字母），讓放最多的大炮，大炮與大炮間不會互相攻擊。

【解析】可以發(fā)現(xiàn)，對于每一行放大炮的狀態(tài)，只與它上面一行和上上一行的狀態(tài)有關(guān)，每一行用狀態(tài)壓縮的表示方法，0表示不放大炮，1表示放大炮，同樣的，先要滿足硬件條件，即有的地方不能放大炮，然后就是每一行中不能有兩個1的距離小于2（保證橫著不互相攻擊），這些要預(yù)先處理一下。然后就是狀態(tài)表示和轉(zhuǎn)移的問題了，因為是和前兩行的狀態(tài)有關(guān)，所以要開個三維的數(shù)組來表示狀態(tài)，當(dāng)前行的狀態(tài)可由前兩行的狀態(tài)轉(zhuǎn)移而來。即如果當(dāng)前行的狀態(tài)符合前兩行的約束條件（不和前兩行的大炮互相攻擊），則當(dāng)前行的最大值就是上一個狀態(tài)的值加上當(dāng)前狀態(tài)中1的個數(shù)（當(dāng)前行放大炮的個數(shù)）

【狀態(tài)表示】dp[i][j][k] 表示第i行狀態(tài)為k，第i-1狀態(tài)為j時的最大炮兵個數(shù)。

【狀態(tài)轉(zhuǎn)移方程】dp[i][k][t] =max(dp[i][k][t],dp[i-1][j][k]+num[t]); num[t]為t狀態(tài)中1的個數(shù)

【DP邊界條件】dp[1][1][i] =num[i] 狀態(tài)i能夠滿足第一行的硬件條件（注意：這里的i指的是第i個狀態(tài)，不是一個二進制數(shù)，開一個數(shù)組保存二進制狀態(tài)）

【代碼】

#include <cstdio> #include <cstring> using namespace std; #define max(a,b) (a) > (b) ? (a) : (b)int N,M; char map[110][20],num[110],top; int stk[70],cur[110]; int dp[110][70][70];inline bool ok(int x){ //判斷該狀態(tài)是否合法，即不存在相鄰的1之間的距離小于3的if(x&(x<<1)) return 0;if(x&(x<<2)) return 0;return 1; } //找到所有可能的合法狀態(tài)，最多60種 inline void jinit() {top=0;int i,total=1<<N;for(i=0;i<total;i++) if(ok(i)) stk[++top]=i; } //判斷狀態(tài)x是否與第k行匹配 inline bool fit(int x,int k) {if(cur[k]&x) return 0;return 1; } //數(shù)一個整型數(shù)x的二進制中1的個數(shù)(用于初始化) inline int jcount(int x) {int cnt=0;while(x){cnt++;x&=(x-1);}return cnt; }int main(){while(scanf("%d%d",&M,&N) != EOF){if(N == 0 && M == 0)break;jinit();for(int i = 1; i <= M; ++i)scanf("%s",map[i]+1);for(int i = 1; i <= M; ++i)for(int j = 1; j <= N; ++j){cur[i]=0;for(j=1;j<=N;j++){if(map[i][j]=='H')cur[i]+=(1<<(j-1));}}memset(dp,-1,sizeof(dp));//初始化第一行狀態(tài)for(int i = 1;i <= top;i++){num[i]=jcount(stk[i]);if(fit(stk[i],1))dp[1][1][i]=num[i];}int i,t,j,k;for(i = 2;i <= M;i++){for(t = 1;t <= top;t++){if(!fit(stk[t],i)) continue;for(j = 1;j <= top;j++){if(stk[t]&stk[j])continue;for(k = 1;k <= top;k++){if(stk[t]&stk[k])continue;if(dp[i-1][j][k]==-1)continue;dp[i][k][t] =max(dp[i][k][t],dp[i-1][j][k]+num[t]);}}}}int ans = 0;for(i = 1; i <= M; ++i)for(j = 1; j <= top; ++j)for(k = 1; k <= top; ++k)ans = max(ans,dp[i][j][k]);printf("%d\n",ans);}return 0; }

【POJ3311】Hie With The Pie

【題目大意】類似于TSP問題，只是每個點可以走多次，比經(jīng)典TSP問題不同的是要先用弗洛伊的預(yù)處理一下兩兩之間的距離。求最短距離。

【解析】可以用全排列做，求出一個最短的距離即可。或者用狀態(tài)壓縮DP.用一個二進制數(shù)表示城市是否走過

【狀態(tài)表示】dp[state][i]表示到達i點狀態(tài)為state的最短距離

【狀態(tài)轉(zhuǎn)移方程】dp[state][i] =min{dp[state][i],dp[state’][j]+dis[j][i]} dis[j][i]為j到i的最短距離

【DP邊界條件】dp[state][i] =dis[0][i] state是只經(jīng)過i的狀態(tài)

【代碼】

#include<iostream> #define INF 100000000 using namespace std; int dis[12][12]; int dp[1<<11][12]; int n,ans,_min; int main() { //freopen("in.txt","r",stdin); while(scanf("%d",&n) && n) { for(int i = 0;i <= n;++i) for(int j = 0;j <= n;++j) scanf("%d",&dis[i][j]); for(int k = 0;k <= n;++k) for(int i = 0;i <= n;++i) for(int j = 0;j <=n;++j) if(dis[i][k] + dis[k][j]< dis[i][j]) dis[i][j] = dis[i][k] +dis[k][j]; for(int S = 0;S <= (1<<n)-1;++S)//枚舉所有狀態(tài)，用位運算表示 for(int i = 1;i <= n;++i) { if(S & (1<<(i-1)))//狀態(tài)S中已經(jīng)過城市i { if(S ==(1<<(i-1))) dp[S][i] =dis[0][i];//狀態(tài)S只經(jīng)過城市I，最優(yōu)解自然是從0出發(fā)到i的dis,這也是DP的邊界else//如果S有經(jīng)過多個城市 { dp[S][i] = INF; for(int j = 1;j <=n;++j) { if(S &(1<<(j-1)) && j != i)//枚舉不是城市I的其他城市 dp[S][i] =min(dp[S^(1<<(i-1))][j] + dis[j][i],dp[S][i]); //在沒經(jīng)過城市I的狀態(tài)中，尋找合適的中間點J使得距離更短} } } } ans = dp[(1<<n)-1][1] + dis[1][0]; for(int i = 2;i <= n;++i) if(dp[(1<<n)-1][i] + dis[i][0] < ans) ans = dp[(1<<n)-1][i] +dis[i][0]; printf("%d\n",ans); } return 0; }

【HDU3001】Traveling

【題目大意】10個點的TSP問題，但是要求每個點最多走兩邊，不是只可以走一次，所以要用三進制的狀態(tài)壓縮解決這個問題。可以預(yù)處理每個狀態(tài)的第k位是什么。

【解析】和tsp問題相同,類似于上面那個題

【狀態(tài)表示】【狀態(tài)轉(zhuǎn)移方程】同上題，具體見代碼

【代碼】

#include <cstdio> #include <cstring> #define INF 0x1f1f1f1f //剛發(fā)現(xiàn)這里寫0x1f1f1f跑的比0x1f1f1f1f差不多慢了一倍！Orz~ #define min(a,b) (a) < (b) ? (a) : (b) using namespace std;int N,M; int tri[12] ={0,1,3,9,27,81,243,729,2187,6561,19683,59049}; int dig[59050][11]; //dig[state][k_dig] 狀態(tài)state的第k位是多少 int edge[11][11],dp[59050][11];int main(){for(int i = 0; i < 59050; ++i){int t = i;for(int j = 1; j <= 10; ++j){dig[i][j] = t%3;t /= 3;if(t == 0)break;}}while(scanf("%d%d",&N,&M) != EOF){memset(edge,INF,sizeof(edge));int a,b,c;while(M --){scanf("%d%d%d",&a,&b,&c);if(c < edge[a][b])edge[a][b] = edge[b][a] = c;}memset(dp,INF,sizeof(dp));for(int i = 1; i <= N; ++i)dp[tri[i]][i] = 0;int ans = INF;for(int S = 0; S < tri[N+1]; ++S){int visit_all = 1;for(int i = 1; i <= N; ++i){if(dig[S][i] == 0)visit_all = 0;if(dp[S][i] == INF)continue;for(int j = 1; j <= N; ++j){if(i == j)continue;if(edge[i][j] == INF ||dig[S][j] >= 2)continue;int newS = S + tri[j];dp[newS][j] =min(dp[newS][j],dp[S][i] + edge[i][j]);}}if(visit_all){for(int j = 1; j <= N; ++j)ans = min(ans,dp[S][j]);}}if(ans == INF){puts("-1");continue;}printf("%d\n",ans);}return 0; }

【POJ2288】Islands and Bridge

【題目大意】求漢密爾頓的一道變形問題，中間每個點有權(quán)值，關(guān)于最后得分的描述如下

Suppose there are n islands. The value of aHamilton path C1C2…Cn is calculated as the sum of three parts. Let Vi be thevalue for the island Ci. As the first part, we sum over all the Vi values foreach island in the path. For the second part, for each edge CiCi+1 in the path,we add the product ViVi+1. And for the third part, whenever three consecutiveislands CiCi+1Ci+2 in the path forms a triangle in the map, i.e. there is abridge between Ci and Ci+2, we add the product ViVi+1*Vi+2.

這題要求讓得分最高

【解析】發(fā)現(xiàn)每個點的狀態(tài)由前面兩個點確定，用DP（S,A,B）表示狀態(tài)為S時，當(dāng)前到達A，而上一個點是B時的最大得分，這個狀態(tài)由DP（S’,B,C）通過從B走到A得到，S’=S-(1<<A),即S’狀態(tài)就是經(jīng)過B和C但不經(jīng)過A的一個狀態(tài)，C是不同于A和B的一個點。

【狀態(tài)轉(zhuǎn)移】dp[S][A][B] =max(dp[S][A][B],dp[S’][B][C]+temp) 這里的temp指的是加上的得分即VbVa+Va,如果構(gòu)成三角關(guān)系（即A和C間有邊），temp就要再加上VbVa*Vc.

【邊界條件】DP((1<<A)+(1<<B),A,B)=Va+Vb+Va*Vb(A和B間有邊)表示

【代碼】

#include <cstdio> #include <cstring> using namespace std; const int MAXN = 13; const int MAX_S = 1<<(MAXN+1); long long dp[MAX_S][MAXN+1][MAXN+1]; long long way[MAX_S][MAXN+1][MAXN+1]; int edge[MAXN+1][MAXN+1]; long long V[MAXN+1];int N,M; int main(){int cas;scanf("%d",&cas);while(cas --){memset(edge,0,sizeof(edge));scanf("%d%d",&N,&M);for(int i = 1; i <= N; ++i)scanf("%d",&V[i]);if(N == 1){printf("%d 1\n",V[1]);continue;}int a,b;while(M --){scanf("%d%d",&a,&b);edge[a][b] = edge[b][a] = 1;}memset(dp,-1,sizeof(dp));memset(way,0,sizeof(way));int ii,jj;long long temp;for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j){if(i == j || !edge[i][j])continue;ii = 1<<(i-1);jj = 1<<(j-1);temp = V[i]+V[j]+V[i]*V[j];dp[ii+jj][i][j] = temp;way[ii+jj][i][j] = 1;}for(int S = 0; S < (1<<N); ++S)for(int i = 1; i <= N; ++i){if((S&(1<<(i-1))) == 0)continue;for(int j = 1; j <= N; ++j){if((S&(1<<(j-1))) ==0 || i == j || !edge[i][j])continue;for(int k = 1; k <= N; ++k){if(i == k || j == k ||(S&(1<<(k-1))) == 0)continue;int newS = S -(1<<(i-1));if(dp[newS][j][k] ==-1)continue;if(!edge[j][k])continue;temp =V[i]+V[i]*V[j]+dp[newS][j][k];if(edge[i][k])temp +=V[i]*V[j]*V[k];if(dp[S][i][j] < temp){dp[S][i][j] = temp;way[S][i][j] =way[newS][j][k]; //如果dp更新，way直接更新}//如果dp不更新，但dp=temp，way加上原來的值else if(temp ==dp[S][i][j])way[S][i][j] += way[newS][j][k];}}}long long ans = -1,num = 0;int p = (1<<(N)) - 1;for (int i = 1; i <= N; ++i)for (int j = 1; j <= N; ++j){if(i == j)continue;if (ans < dp[p][i][j]){ans = dp[p][i][j];num = way[p][i][j];}else if (ans == dp[p][i][j])num += way[p][i][j];}if(ans == -1){puts("0 0");continue;}printf("%lld %lld\n",ans,num/2);}return 0; }

【ZOJ4257】MostPowerful

【題目大意】不超過10種氣體，兩兩之間相互碰撞可以產(chǎn)生一定的能量，如a碰b，那么b氣體就消失，自身不能碰自身，問最后所能得到的最大能量。

【題目解析】用10位二進制表示氣體是否存在，0表示存在，1表示不存在，S（上一個狀態(tài)）中的兩種氣體碰撞并且有一種消失，可以得到newS的狀態(tài)（狀態(tài)轉(zhuǎn)移）

【狀態(tài)表示】dp[state] 狀態(tài)為state時的最大能量

【轉(zhuǎn)移方程】dp[state] = max(dp[state],dp[state’]+a[i][j])

【邊界條件】dp[i] = 0;

【代碼】

#include <cstdio>#include <cstring>using namespace std;#define max(a,b) (a) > (b) ? (a) : (b)const int MAXN = 10;const int MAX_S = 1 << 10;int a[MAXN+1][MAXN+1];int dp[MAX_S];int N;int main(){while(scanf("%d",&N) != EOF){if(N == 0)break;for(int i = 0; i < N; ++i)for(int j = 0; j < N; ++j){scanf("%d",&a[i][j]);}memset(dp,0,sizeof(dp));int full = 1 << N;for(int s = 0; s < full; ++s){for(int i = 0; i < N; ++i){if((s&(1<<i)))continue;for(int j = 0; j < N; ++j){if(i == j)continue;if( (s&(1<<j)) )continue;int newS = s + (1<<j);dp[newS] = max(dp[newS],dp[s] + a[i][j]);}}}int ans = 0;for(int s = 0; s < full ; ++s)ans = max(ans,dp[s]);printf("%d\n",ans);}return 0;}

【POJ2411】Mondriaan’sDream

【題目大意】一個矩陣，只能放1*2的木塊，問將這個矩陣完全覆蓋的不同放法有多少種。

【解析】如果是橫著的就定義11，如果豎著的定義為豎著的01，這樣按行dp只需要考慮兩件事兒，當(dāng)前行&上一行，是不是全為1，不是說明豎著有空（不可能出現(xiàn)豎著的00），另一個要檢查當(dāng)前行里有沒有橫放的，但為奇數(shù)的1。

【狀態(tài)表示】dp[state][i]第i行狀態(tài)為state時候的方案數(shù)

【轉(zhuǎn)移方程】dp[state][i] += dp[state’][i-1] state’為i-1行的，不與i行狀態(tài)state沖突的狀態(tài)

【邊界條件】第一行 符合條件的狀態(tài)記為1 即dp[state][0] = 1;

【代碼】

#include <cstdio>#include <cstring>using namespace std;int M,N;long long dp[1<<11][11];bool kexing[1<<11];int full;inline bool check(int in){int bit=0;while(in>0){if( (in&1)==1)bit++;else{if( (bit&1)==1)return false;bit=0;}in>>=1;}if( (bit&1)==1)return false;return true;}inline bool check2(int x1,int x2){if( (x1|x2)!= full-1 ) //如果這里不用位運算，時間很長，要用約3000MSreturn false;return kexing[x1&x2];}int main(){full = 1<<11;for(int s = 0; s < full; ++s)if(check(s))kexing[s] = 1;while(scanf("%d%d",&M,&N) != EOF){if(N == 0 && M == 0)break;memset(dp,0,sizeof(dp));full = 1<<N;for(int s = 0; s < full; ++s){if(kexing[s])dp[s][0] = 1;}for(int i = 1; i < M; ++i){for(int s = 0; s < full; ++s){for(int s1 = 0; s1 < full; ++s1){if(!check2(s1,s))continue;//if(dp[s1][i-1] == 0)continue; /*這一步判斷的時間要大于位運算和+=的時間，如果先把這一步放在check2前面，1300多MS，如果放在check2后面，610多MS，如果不加這一步，560MS，但如果check2用的不是位運算，將這一步加在check2前面3000MS左右（水過），如果不加這一步，TLE*/dp[s][i] += dp[s1][i-1];}}}int S = (1<<N) - 1;printf("%lld\n",dp[S][M-1]);}return 0;}

【HDU3681】PrisonBreak 狀態(tài)壓縮DP+BFS+二分答案

2010杭州賽區(qū)的題目，以現(xiàn)在的水平遇到這種題也就能想一下，賽場上動手寫這個題是不會的。前天做狀壓DP的時候又看到這個題，沒想起來怎么做，昨天看了一下解題報告開始下手，遇到了各種問題。調(diào)試了N久，終于過了。

【題目大意】機器人從F出發(fā)，走到G可以充電，走到Y(jié)關(guān)掉開關(guān)，D不能走進，要求把所有開關(guān)關(guān)掉，且電量最少，并求出該最小電量。

【題目解析】機器人從出發(fā)點出發(fā)要求走過所有的Y，因為點很少，所以就能想到經(jīng)典的TSP問題（起初我也想到了），但關(guān)于G點（不要YY）能充電的問題不知道怎么辦，看了下解題報告才知道。G點可以充電，到達G點就把當(dāng)前能量更新為電池容量然后繼續(xù)走。因為每個G點只能充一次電，這就好像TSP中的每個點只能走一次一樣（G和Y都可以走多次，但走到G充電后，該點就變?yōu)榱薙，而走到Y(jié)關(guān)上開關(guān)以后，Y也變成了S。這是一個很巧妙地想法，所以要求Y點只能關(guān)一次開關(guān)，G點只能充一次電，這就是TSP了。Orz賽場上可以秒殺這題的大神們），然后就是二分答案了，用狀壓DP判定當(dāng)前電池容量的情況下是否能符合條件。

【狀態(tài)表示】dp[s][i]表示到達當(dāng)前i點狀態(tài)為s時最大的剩余的能量

【轉(zhuǎn)移方程】同TSP問題了

【邊界條件】dp[1<<sid][sid] = rongliang.即出發(fā)點的能量就是電池容量

【代碼】：

#include <cstdio>#include <cstring>#include <cmath>#include <queue>using namespace std;#define INF 0x1f1f1f1fint dp[32769][16];int dist[16][16][16][16];int di[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};int M,N,sid,nCnt,FinalState;char map[16][16];struct node{int x,y;node(){}node(int _x,int _y):x(_x),y(_y){}}nodes[16];inline void BFS(node start){queue<node> que;int sx = start.x,sy = start.y;dist[sx][sy][sx][sy] = 0;que.push(start);node cur;while(!que.empty()){cur = que.front();que.pop();int x = cur.x,y = cur.y,tx,ty;for(int i = 0; i < 4; ++i){tx = x + di[i][0];ty = y + di[i][1];if(tx < 0 || tx >= M || ty < 0 || ty >= N || map[tx][ty] == 'D')continue;if(dist[sx][sy][tx][ty] == -1){dist[sx][sy][tx][ty] = dist[sx][sy][x][y] + 1;que.push(node(tx,ty));}}}}inline bool ok(int s,int t){ //s狀態(tài)中走過所有t狀態(tài)中的城市if(((s&t)&t) == t)return 1;return 0; } inline bool check(int step){ int res = -1; memset(dp,-1,sizeof(dp)); dp[1<<sid][sid] = step; int full = 1<<nCnt; for(int s = 0; s < full; ++s){for(int i = 0; i < nCnt; ++i){ if((s&(1<<i)) == 0 || dp[s][i] == -1)continue; if(ok(s,FinalState))res = max(res,dp[s][i]); for(int j = 0; j < nCnt; ++j){ int temp = dist[nodes[i].x][nodes[i].y][nodes[j].x][nodes[j].y]; if(i == j || temp == -1 || (s&(1<<j)))continue; temp = dp[s][i] - temp; if(temp < 0)continue; int newS = s + (1<<j); dp[newS][j] = max(dp[newS][j],temp); if(map[nodes[j].x][nodes[j].y] == 'G')dp[newS][j] = step;}}}if(res < 0)return 0;return 1;}inline int solve(){int low = 0,high = 300;int mid;while(low <= high){mid = (low+high)/2;if(check(mid))high = mid-1;else low = mid+1;}if(low == 301)return -1;return low;}int main(){while(scanf("%d%d",&M,&N) != EOF){if(M == 0 && N == 0)break;nCnt = 0;FinalState = 0;for(int i = 0; i < M; ++i){scanf(" %s",map[i]);for(int j = 0; j < N; ++j){if(map[i][j] == 'F'){sid = nCnt;nodes[nCnt++] = node(i,j);FinalState += (1<<sid);}else if(map[i][j] == 'G')nodes[nCnt++] = node(i,j);else if(map[i][j] == 'Y'){int tid = nCnt;nodes[nCnt++] = node(i,j);FinalState += (1<<tid);}}}memset(dist,-1,sizeof(dist));for(int i = 0; i < nCnt; ++i)BFS(nodes[i]);int ans = solve();printf("%d\n",ans);}return 0;}

---

總結(jié)

以上是生活随笔為你收集整理的状态压缩DP（大佬写的很好，转来看）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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