codeforces 111C Petya and Spiders - c++编程基础

一个n*m的棋盘，初始状态下每个格子上都有一只蜘蛛，蜘蛛一步可以上下左右走，也可以停在原地，问，走一步，能使棋盘最多产生多少个空位

考虑到n*m较小，所以有一维<=6，这时候就应该想到可以用状态压缩DP解决

dp[i][j][k]表示前i行，第i行的状态为j，第i+1行的状态为k时所能产生的最多空位的数量（不包括第i+1行），由于不包括第i+1行，所以在状态转移判断某些状态能否转移过来的时候就简单多了，只需要判断中间那一行能否恢复成初始状态即可（也就是当前状态能否从初始状态变过来）

参考代码

[cpp]

#include

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 VI;

typedef vector VS;

typedef pair PII;

#define rep(i,n) for(int i=0;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 T two(T x) {return 1<

template void Min(T &x, T y){if(y < x) x = y;}

template 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<

}