一個n*m的棋盤，初始狀態下每個格子上都有一只蜘蛛，蜘蛛一步可以上下左右走，也可以停在原地，問，走一步，能使棋盤最多產生多少個空位 考慮到n*m較小，所以有一維<=6，這時候就應該想到可以用狀態壓縮DP解決 dp[i][j][k]表示前i行，第i行的狀態為j，第i+1行的狀態為k時所能產生的最多空位的數量（不包括第i+1行），由於不包括第i+1行，所以在狀態轉移判斷某些狀態能否轉移過來的時候就簡單多了，只需要判斷中間那一行能否恢復成初始狀態即可（也就是當前狀態能否從初始狀態變過來） 參考代碼 [cpp] #include <cstdio> #include <cstring> #include <set> #include <string> #include <iostream> #include <cmath> #include <vector> #include <map> #include <stack> #include <time.h> #include <queue> #include <cstdlib> #include <algorithm> using namespace std; #define lowbit(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) #define PB push_back #define MP make_pair #define foreach(it, x) for(typeof(x.begin()) it = x.begin(); it!=x.end();it++) typedef unsigned long long ULL; typedef long long lld; typedef vector<int> VI; typedef vector<string> VS; typedef pair<int,int> PII; #define rep(i,n) for(int i=0;i<n;i++) #define For(i,a,b) for(int i=a;i<=b;i++) #define CL(x) memset(x, 0, sizeof(x)) #define CLX(x, y) memset(x, y, sizeof(x)) template <class T> T two(T x) {return 1<<x ;} template <class T> void Min(T &x, T y){if(y < x) x = y;} template <class T> void Max(T &x,T y){if(y > x) x = y;} int dp[45][1<<6][1<<6],n,m; int full; inline int get(int x) { int cnt = 0; rep(i,m) if(x>>i&1) cnt++; return m - cnt; } bool check(int a,int b,int c) { int s = b | (b<<1) | (b>>1) | a | c; return ( s & (full-1) )== (full-1); } int State[1<<6]; int main() { scanf("%d%d",&n,&m); if(n < m) swap(n,m); www.2cto.com full = two(m) ; rep(i,n+1) rep(j,full) rep(k,full) dp[i][j][k] = -111111; rep(i,full) dp[0][0][i] = 0,State[i] = get(i); rep(i,n) rep(j,full) rep(k,full) rep(l,full) if(check(j,k,l)) Max( dp[i+1][k][l] , dp[i][j][k] + State[k] ); int ans = 0; rep(i,full) Max(ans,dp[n][i][0]); cout<<ans<<endl; }
