POJ 1185 炮兵阵地
一般这类题目列会很小10左右，我们需要枚举所有行，对于当前行，其放炮的位置只与上一行和上上行有关，我们记当前行状态和上一行状态便可转移了，dp数组开3维即可。
在枚举每一行放炮兵的方法时，可以预处理方便获得所有可能放法。具体细节见代码。总体复杂度O(Row*70*70*70)，70是预处理得到的每一行最多放法。打表很容易看出来。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char map[105][12];
int n,m,hmap[105],shell[70],permutation[70],all,dp[2][70][70];
void init(){
int i,k;
all=0;
memset(shell,0,sizeof(shell));
for(i=0;i<1<<m;i++){
k=i;
if( (i&(k>>1)) || (i&(k>>2)) )
continue;
shell[all]+=k%2;
k/=2;
while(k!=0){
shell[all]+=k%2;
k/=2;
}
permutation[all++]=i;
}
}
void dps(){
int row,i,j,k,h,max=0;
memset(dp,0,sizeof(dp));
row=0;
for(i=0;i<n;i++){
for(j=0;j<all;j++){
if(permutation[j]&hmap[i])
continue;
if(i==0){
dp[row][j][0]=shell[j];
}
else if(i==1){
for(k=0;k<all;k++){
if(permutation[k]&hmap[i-1]){
continue;
}
if(permutation[k]&permutation[j]){
continue;
}
if(dp[row][j][k]<dp[(row+1)%2][k][0]+shell[j])
dp[row][j][k]=dp[(row+1)%2][k][0]+shell[j];
}
}
else{
for(k=0;k<all;k++){
if(permutation[k]&hmap[i-1]){
continue;
}
if(permutation[k]&permutation[j]){
continue;
}
for(h=0;h<all;h++){
if(permutation[h]&hmap[i-2]){
continue;
}
if(permutation[h]&permutation[j]){
continue;
}
if(permutation[h]&permutation[j]){
continue;
}
if(dp[row][j][k]<dp[(row+1)%2][k][h]+shell[j])
dp[row][j][k]=dp[(row+1)%2][k][h]+shell[j];
}
}
}
}
row=(row+1)%2;
}
for(i=0;i<all;i++){
for(j=0;j<all;j++){
if(max<dp[(row+1)%2][i][j])
max=dp[(row+1)%2][i][j];
}
}
printf("%d\n",max);
}
int main()
{
int i,j,k;
scanf("%d %d",&n,&m);
memset(hmap,0,sizeof(hmap));
for(i=0;i<n;i++)
scanf("%s",map[i]);
for(i=0;i<n;i++){
for(j=0;j<m;j++){
if(map[i][j]==‘H‘)
hmap[i]+=1<<j;
}
}
init();
dps();
}
zoj 3755Mines
前几天的浙大月赛真题。
逐行扫描，取最小值的简单状压DP
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int mp[11][11];
int dp[2][1024];
int num[1024];
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&mp[i][j]);
int now=0;
int sta=1<<n;
for(int i=0;i<sta;i++){
num[i]=0;
for(int j=0;j<n;j++) num[i]+=(i&(1<<j))?1:0;
dp[now][i]=num[i];
}
now=!now;
for(int t=0;t<m;t++){
memset(dp[now],-1,sizeof(dp[now]));
for(int i=0;i<sta;i++)
for(int j=0;j<sta;j++){
if(dp[!now][j]==-1)continue;
int tmp[11];
for(int k=0;k<n;k++)tmp[k]=((i&(1<<k))?1:0)+((j&(1<<k))?1:0);
bool flag=1;
if((tmp[0]+tmp[1])!=mp[0][t])flag=0;
int k;
for(k=1;k<n-1 && flag;k++){
if((tmp[k-1]+tmp[k]+tmp[k+1])!=mp[k][t])flag=0;
}
if(k==n-1 && (tmp[k-1]+tmp[k])!=mp[k][t])flag=0;
if(flag){
if(dp[now][i]==-1)dp[now][i]=dp[!now][j]+num[i];
else dp[now][i]=min(dp[now][i],dp[!now][j]+num[i]);
}
}
now=!now;
}
int ans=-1;
for(int i=0;i<1024;i++)if(dp[!now][i]!=-1){
if(ans==-1) ans=dp[!now][i];
else ans=min(ans,dp[!now][i]);
}
printf("%d\n",ans);
}
}
这类题目有两种做法，一是直接按行状压，另外一种是轮廓线法（因为矩形是1*2的，所以轮廓线只需要维护长为列长的状态即可2^10），
状压做法如下（代码转自http://blog.csdn.net/xiaozhuaixifu/article/details/10221341）
先初始化第一行的方法，2^10判断每个状态是否合法并记录。然后处理其他行时，要满足当前行的前面所有行都匹配好即可，所以状态只需要记录二维，转移时判断当前行的状态nStatusA能否补上上一行状态nStatusB漏掉的格子并且剩余的nStatusA是1*2的矩形拼成的即可。总体复杂度O(Row*(2^Col)*(2^Col)*Col)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
#define MAX_ROW 11
#define MAX_STATUS 2048
long long DP[MAX_ROW][MAX_STATUS];
int g_Width, g_Height;
bool TestFirstLine(int nStatus) //test the first line
{
int i = 0;
while( i < g_Width)
{
if(nStatus & (0x1 << i))
{
if( i == g_Width -1 || (nStatus & (0x1 << (i+1))) == 0)
{
return false;
}
i += 2;
}
else
{
i++;
}
}
return true;
}
bool CompatablityTest(int nStatusA, int nStatusB) // test if status (i, nStatusA) and (i-1, nStatusB) is compatable.
{
int i = 0;
while( i < g_Width)
{
if( (nStatusA & (0x1 << i)) == 0)
{
if((nStatusB & (0x1 << i)) == 0)
{
return false;
}
i++;
}
else
{
if((nStatusB & (0x1 << i)) == 0 )
{
i++;
}
else if( (i == g_Width - 1) || ! ( (nStatusA & (0x1 << (i+1))) && (nStatusB & (0x1 << (i + 1)))) )
{
return false;
}
else
{
i += 2;
}
}
}
return true;
}
int main()
{
int i,j;
int k;
while(scanf("%d%d", &g_Height, &g_Width) != EOF )
{
if(g_Width == 0 && g_Height == 0)
{
break;
}
if(g_Width > g_Height)
{
swap(g_Width, g_Height);
}
int nAllStatus = 2 << (g_Width-1);
memset(DP, 0, sizeof(DP));
for( j = 0; j < nAllStatus; j++)
{
if(TestFirstLine(j))
{
DP[0][j] = 1;
}
}
for( i = 1; i < g_Height; i++)
{
for( j = 0; j < nAllStatus; j++)// iterate all status for line i
{
for( k = 0; k < nAllStatus; k++) // iterate all status for line i-1
{
if(CompatablityTest(j, k))
{
DP[i][j] += DP[i-1][k];
}
}
}
}
printf("%lld\n", DP[g_Height-1][nAllStatus - 1]);
}
return 0;
}
轮廓线做法（转自http://blog.csdn.net/cc_again/article/details/9390475）
简单轮廓线dp，时刻记录一个长为Col的轮廓线即可，转移也比较简单，当前不放，朝上的矩形，朝左的矩形三种情况讨论一下即可。总体复杂度O(Row*Col*(2^Col))。可以看出来轮廓线做法复杂度更优！
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
ll dp[2][1<<15]; //dp[cur][s]表示当前格子的轮廓线状态为s的情况下的总数
int n,m,cur;
void update(int a,int b)
{
if(b&(1<<m)) //将前一个格子的最高位，如果是1,则置零，并更新
dp[cur][b^(1<<m)]+=dp[1-cur][a];
}
int main()
{
while(scanf("%d%d",&n,&m)&&m+n)
{
//if(m+n)
if(m>n)
swap(n,m);
memset(dp,0,sizeof(dp));
dp[0][(1<<m)-1]=1; //第一行只能横着放，把这个状态初始化为1
cur=0;
int lim=1<<m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) //对每个格子，从前面一个格子推过来
{
cur^=1;
memset(dp[cur],0,sizeof(dp[cur]));
for(int k=0;k<lim;k++) //枚举前一个格子的所有状态
{
update(k,k<<1); //不放
if(i&&!(k&(1<<(m-1))))//竖着放
update(k,(k<<1)^(1<<m)^1); //将放着的两点置1
if(j&&!(k&1))
update(k,(k<<1)^3); //横着放
}
}
printf("%lld\n",dp[cur][lim-1]);
}
return 0;
}
hdu 4804 Campus Design
同样这题和上题类似，也有两种做法。
直接状压法。（转自http://www.cnblogs.com/wulangzhou/p/3451756.html）
这个思想也和上一个题目类似，在本行内用1*1和1*2横放填充（这个用dfs实现），在行间转移原则是本行要先用1*2的竖放把上一行的状态填满，然后再在剩下的格子里用1*1和1*2横放填充即可。总体复杂度O(Row*(2^Col)*(2^Col)*D)，当然由于行间转移时转移到的状态数是小于(2^Col)的，所以8s的时限凑合可以。
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
#define mod 1000000007
using namespace std;
int N,M,C,D;
__int64 dp[4][3000][22];
char map[105][22];
void dfs( int sta,int lev,int stu,int n,int k,__int64 num )
{
if( sta >= M || k > D)return;
dfs( sta+1,lev,stu,n,k,num );
if( map[lev][sta] == ‘1‘ && (stu&(1<<sta)) == 0 )
{
int t = stu+(1<<sta);
dp[n][t][k+1]+=num; dp[n][t][k+1] %= mod;
dfs(sta+1,lev,t,n,k+1,num);
}
if( sta + 1 < M && map[lev][sta] == ‘1‘ && map[lev][sta+1] == ‘1‘ )
if( (stu&(1<<sta)) == 0 && (stu&(1<<(sta+1))) == 0 )
{
int t = stu+(1<<sta); t = t+(1<<(sta+1));
dp[n][t][k]+=num; dp[n][t][k] %= mod;
dfs(sta+2,lev,t,n,k,num);
}
}
void work( )
{
int i,j,k,s,t=1,num = (1<<M); memset( dp,0,sizeof(dp) ); dp[t][num-1][0] = 1;
for( i = 1; i <= N; i++ )
{
s = t^1;
for( j = 0; j < num; j++ )
for( k = 0; k <= D; k++ )
{
if( dp[t][j][k] == 0 )continue; __int64 stu = 0; bool fell = false;
for( int x = 0; x < M; x++ )
if( map[i-1][x] != ‘0‘ && (j&(1<<x)) == 0 )
{
if( map[i][x] == ‘0‘ ) fell = true;
else stu += (1<<x);
}
if( fell )continue;
dp[s][stu][k] = dp[t][j][k];
dfs( 0,i,stu,s,k,dp[t][j][k] );
}
for( j = 0; j < num; j++ )
for( k = 0; k <= D; k++ )
dp[t][j][k] = 0;
t = s;
}
__int64 res = 0; int now = 0;
for( j = 0; j < M; j++ )if( map[N][j] != ‘0‘ ) now +=(1<<j);
for( j = C; j <= D; j++ ) res += dp[t][now][j],res %= mod;
printf("%I64d\n",res);
}
int main( )
{
while( scanf("%d%d%d%d",&N,&M,&C,&D) != EOF ){
memset(map,‘0‘,sizeof(map));
for( int i = 1; i <= N; i++ )
scanf("%s",map[i]);
work( );
}
return 0;
}
轮廓线算法（转自http://blog.csdn.net/guognib/article/details/17045017?reload）
这个做法也类似啦...转移清楚明了，可见这种做法的优越性，总体复杂度O(Row*Col*(2^Col)*D)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define PB push_back
#define LL long long
using namespace std;
const int MOD = 1e9 + 7;
int n, m;
int C, D;
int dp[2][1 << 10][22];
char ch[110][20];
int now, next;
int ALL;
void update(int nexts, int s, int nextk, int k)
{
if (nexts & (1 << m))///转移时的条件，必须保证转移后，之前的格子，都被覆盖
{
dp[next][nexts ^ (1 << m)][nextk] += dp[now][s][k];
if (dp[next][nexts ^ (1 << m)][nextk] >= MOD) dp[next][nexts ^ (1 << m)][nextk] %= MOD;
}
}
int main()
{
while (scanf("%d%d%d%d", &n, &m, &C, &D) != EOF)
{
REP(i, n) scanf("%s", ch[i]);
CLR(dp, 0);
now = 0;
ALL = (1 << m) - 1;
dp[0][ALL][0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
next = now ^ 1;
if (ch[i][j] == ‘0‘)/// 不可放时的转移
{
for (int k = 0; k <= D; k++) for (int s = 0; s <= ALL; s++)
if (dp[now][s][k]) update((s << 1) ^ 1, s, k, k);
}
else///可以放时的转移
{
for (int k = 0; k <= D; k++) for (int s = 0; s <= ALL; s++)
if (dp[now][s][k])
{
update((s << 1), s, k, k);///此处不放，直接转移
update((s << 1) ^ 1, s, k + 1, k);///放1*1块的转移
if (j && !(s & 1)) update((s << 1) ^ 3, s, k, k);///横着放1*2块时的转移
if (i && !(s & (1 << (m - 1)))) update((s << 1) ^ (1 << m) ^ 1, s, k, k);///竖着放1*2块是的转移
}
}
CLR(dp[now], 0);
now ^= 1;
}
}
int ans = 0;
for (int i = C; i <= D; i++)
{
ans += dp[now][ALL][i];
if (ans >= MOD) ans %= MOD;
}
printf("%d\n", ans);
}
}