以前没做过这种类型的状态压缩DP，刚开始看着没想明白，后来跟着代码看着好多了。
题意：一个矩阵，有一些地方可以放大炮，有的地方不能放，大炮对上下左右的攻击范围都是两格。两个大炮不能互相攻击到，问最多放多少大炮。
思路：求出每一行的所有状态数，即用二进制表示的所有可行状态（1010，选第一个和第三个）。大炮的攻击距离是2，所以本行、上一行、上上一行不能有大炮在同一行。遍历本行、上一行、上上一行，计算并记下可行状态的结果。
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define PB push_back
#define INF 0x7fffffff
int n, m;
int cnt[120];
int now[102],last[102],lastlast[102];
int dp[120][120], lastdp[120][120];
char g[102][12];
int nowsize, lastsize, lastlastsize;
void init(int i, int j, int p, int sum){
if( j > m) { now[nowsize] = p; cnt[nowsize++] = sum; return ;}
if( g[i][j] == 'P' ) init(i, j+3, p|1<<j, sum+1);
init(i, j+1, p, sum);
}
void DP(){
for(int i = 0; i < n; i ++){
nowsize = 0;
init(i,0,0,0);
//cout << nowsize << endl;
memset(dp, 0, sizeof(dp));
for(int j = 0; j < nowsize; j ++) {
for(int k = 0; k < lastsize; k ++){
for(int t = 0; t < lastlastsize; t ++){
if( now[j] & last[k] || now[j] & lastlast[t] || last[k] & lastlast[t]) continue;
dp[j][k] = max(dp[j][k], lastdp[k][t] + cnt[j] );
// lastdp[j][k] = dp[j][k];
}
}
}
int k, j;
For(k, nowsize) For(j, lastsize) lastdp[k][j] = dp[k][j];
for(int j = 0; j < lastsize; j ++) lastlast[j] = last[j]; lastlastsize = lastsize;
for(int j = 0; j < nowsize; j ++) last[j] = now[j]; lastsize = nowsize;
//for(int j = 0; j < nowsize; j ++) lastdp[
}
}
int main(){
while( ~scanf("%d%d",&n,&m)){
for(int i = 0; i < n; i ++) scanf("%s",g[i]);
//memset(lastdp, 0, sizeof(lastdp));
last[0]=lastlast[0]=lastdp[0][0]=0;
lastsize = lastlastsize = 1;
DP();
int ans = 0;
for(int i = 0; i < lastsize; i ++){
for(int j = 0; j < lastlastsize; j ++){
ans = max( ans, lastdp[i][j]);
}
}
cout << ans << endl;
}
return 0;
}
题意：有一个棋盘，棋盘上有些点能放棋子，有些点不可以。一个棋子能够控制相邻的四个位置，两个棋子不能互相控制。求最少多少个棋子能控制全盘？
思路：先学的上面的，根据上面的思路卡在了控制全盘。需要在上面的代码上加入控制的状态，nowvis[i][j] 本行选i上一行选j本行能控制的格子状态。now[i]和last[j]计算的时候上面一行要全部控制到，因为在下面一行不可能控制到last[j]行。最后求全控制的最小值。群里面大神用dancing links 做的，正在学习中……
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define PB push_back
#define INF 0x7fffffff
int ans;
int n, m, all;
bool g[10][10];
int last[100],now[100];
int lastsize, nowsize, lastlastsize;
int cnt[100],dp[110][110],lastdp[100][110];
int bit[10],nowvis[110][110],lastvis[110][110];
int getbit(int p){
int i = 0, res = 0;
while(p){
bit[i++] = p%2;
p /= 2;
}
if( bit[0] == 1) res |= 3;
for(int j = 1; j < i; j ++) if(bit[j] == 1) res |= 7<<j-1;
if(res > all) res = res & (res & all);
return res;
}
void init(int i, int j, int p, int sum){
if( j >= n) { now[nowsize] = p; cnt[nowsize++] = sum; return ;}
if( g[i][j] == 0 ) init(i, j+2, p|1<<j, sum+1);
init(i, j+1, p, sum);
}
void DP(){
for(int i = 0; i < n; i ++){
nowsize = 0;
memset(nowvis,0,sizeof(nowvis));
memset(bit,0,sizeof(bit));
memset(dp, 0x3f, sizeof(dp));
init(i, 0, 0, 0);
for(int j = 0; j < nowsize; j ++){
for(int k = 0; k < lastsize; k ++){
for(int t = 0; t < lastlastsize; t ++){
if( now[j] & last[k] ) continue;
if((lastvis[k][t] | now[j] )== all) {
dp[j][k] = min(dp[j][k], lastdp[k][t] + cnt[j]);
nowvis[j][k] = getbit(now[j]) | last[k];
}
}
}
}
//for(int j = 0; j < nowsize; j ++) {for(int k = 0; k < lastsize; k ++) cout << dp[j][k] << ' ' ;cout <<endl;}cout << endl << endl ;
lastlastsize = lastsize;
for(int j = 0; j < nowsize; j ++) last[j] = now[j];
for(int j = 0; j < nowsize; j ++) for(int k = 0; k < lastsize; k ++) lastdp[j][k] = dp[j][k];
for(int j = 0; j < nowsize; j ++) for(int k = 0; k < lastsize; k ++) lastvis[j][k] = nowvis[j][k];
lastsize = nowsize;
}
}
int main(){
int x, y;
while(cin >> n >> m){
all = 1<< n;
ans = 0x7fffffff;
all --;
memset(g,0,sizeof(g));
for(int i = 0; i < m; i ++) {
cin >> x >> y;
g[x-1][y-1] = 1;
}
last[0] = dp[0][0] = lastdp[0][0] = 0;
lastvis[0][0] = all;
lastsize = lastlastsize = 1;
DP();
for(int i = 0; i < nowsize; i ++){
for(int j = 0; j < lastsize; j ++){
if(lastvis[i][j] == all) ans = min(dp[i][j], ans);
}
}
if( ans > 100) cout << -1 << endl;
else cout << ans << endl;
}
return 0;
}