题目清单
- POJ1185 炮兵布阵（状态压缩dp）
- HDU1693 闭合线路统计（插头dp）
- POJ2411 平面骨牌密铺（状态压缩dp/轮廓线更新）
- HDU1565 矩阵选数（轮廓线更新）
- HDU2167 矩阵选数（比上一题更严格的条件）（轮廓线更新）
POJ1185 该题是状态压缩dp的入门题，通常的做法是用一个01串表示行上某个位置是否安排炮兵。在状态转移时遍历前两行的状态并安排炮兵向下一行转移：对于每一行进行二重循环，分别遍历两行的状态，并进行检测转移合法性。然而考虑到状态数过多（2^10），实际循环遍历轮数是它的平方。所以我们对状态进行预处理，事先将不合法的状态（行内安排间隔小于2）剔除，重新编码，能显著减少状态数（在列数<10的情况下，状态数小于65）。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1024;
int pro[maxn], rev[65], tot;
int dp[2][65][65];
int mp[110];
int n, m;
inline bool judge(int x) { return (x&(x>>1))||(x&(x>>2)); }
// 检查合法状态
void init() {
tot=0;
for (int i=0;i<(1<<m);++i) {
pro[i]=-1;
if (judge(i)) continue;
pro[i]=tot;
rev[tot++]=i;
}
}
int main() {
scanf("%d%d", &n, &m);
init();
mp[0]=0;
for (int i=1;i<=n;++i) {
char tmp[11];
mp[i]=0;
scanf("%s", tmp);
for (int j=m-1;j>=0;--j) {
mp[i]<<=1;
mp[i]+=(tmp[j]=='H');
}
}
memset(dp, 0xff, sizeof(dp));
dp[0][0][0]=0;
for (int i=1;i<=n;++i) {
if (i>1) memset(dp[i%2], 0xff, sizeof(dp[i%2]));
for (int u=0;u<tot;++u) {
//
int last=rev[u];
if (i>2&&(last&mp[i-2])) continue;
if (judge(last)) continue;
for (int v=0;v<tot;++v) {
//
int cur=rev[v];
if (dp[(i+1)%2][u][v]<0) continue;
if (cur&last) continue;
if (i>1&&(cur&mp[i-1])) continue;
if (judge(cur)) continue;
for (int w=0;w<tot;++w) {//rev[v]和rev[w]分别是前两行的状态
int nxt=rev[w];
if (nxt&mp[i]) continue;//位置是山
if ((nxt&cur)||(nxt&last)) continue;//与前面两行有冲突
if (judge(nxt)) continue;
int num=0;
for (int j=0;j<m;++j)//计数
if (nxt&(1<<j)) ++num;
dp[i%2][v][w]=max(dp[i%2][v][w], dp[(i+1)%2][u][v]+num);
}
if (i<2) break;
}
if (i<3) break;
}
}
int ans=0;
for (int i=0;i<tot;++i) {
for (int j=0;j<tot;++j) {
ans=max(ans, dp[n%2][i][j]);
}
}
printf("%d\n", ans);
return 0;
}
POJ1693 在一个相对较小的矩阵中有些位置不可以走，现在只能上、下、左、右访问合法位置，走过的路不可以再走。现在在遵守以上约定的情况下，在矩阵中安排回路，求总的安排种类数。虽然题目中要求每个回路中必须包含一个或多个禁止通行的方块，但是完全没考虑这样的情况提交之后也ac了……
我们考虑这样的状态：对于某个格子u，它所处的行在它左侧的所有格子和在它上方的所有格子已经被统计过，在统计过与未被统计过的格子中间划一条“边缘线”（轮廓线），沿着这个轮廓线，被统计过的格子是否与未被统计的格子之间存在“插头”，将这个记作state，它可以用一个01串表示。所谓“插头”就是是否有跨过轮廓线的路径。dp[u][state]表示统计到u时轮廓线上插头状态为state的时候，总的路径安排种类数。
插头dp01.png
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=13;
int mp[N][N], n, m;
ll dp[2][1<<N];
int main(){
int T, icase=1;
scanf("%d", &T);
while (T--){
scanf("%d%d", &n,&m);
for (int i=0;i<n;++i)
for (int j=0;j<m;++j)scanf("%d",&mp[i][j]);
// DP
int cur=0,pre=1;
memset(dp,0,sizeof dp);
dp[cur][0]=1;
for (int i=0;i<n;++i){
for (int j=0;j<m;++j){
swap(cur,pre);
memset(dp[cur],0,sizeof(dp[cur]));
if (mp[i][j]==0) { // unable to place
for (int st=0;st<(2<<m);++st){
if ((st&(3<<j))==0){
if (j<m-1) dp[cur][st]+=dp[pre][st];
else dp[cur][st<<1]+=dp[pre][st];// next line
}
}
}else{ // able to place
for (int st=0;st<(2<<m);++st){
if (j<m-1){
if ((st&(3<<j))==0) // 00->11
dp[cur][st|(3<<j)]+=dp[pre][st];
else if (((st>>j)&3)!=3) { // 01/10->01/10
dp[cur][st^(3<<j)]+=dp[pre][st];
dp[cur][st]+=dp[pre][st];
}else dp[cur][st^(3<<j)]+=dp[pre][st];
}else{// next line
if (((st>>j)&3)==1||((st>>j)&3)==2) //01 10->10
dp[cur][((st|(1<<j))<<1)&((2<<m)-1)]+=dp[pre][st];
else if (((st>>j)&3)==3) //11->00
dp[cur][(st^(3<<j))<<1]+=dp[pre][st];
}
}
}
}
}
printf("Case %d: There are %lld ways to eat the trees.\n", icase++, dp[cur][0]);
}
return 0;
}
POJ2411 平面骨牌密铺，如果选用和插头dp类似的轮廓线转移方式做，状态转移会比较方便，因为状态转移到另一种状态的种类数有限。此次记录轮廓线下方（与上题不同，轮廓线上有段竖直的线状态不计）的方块是否已经被占用，进行状态转移。大体与上一题类似。
#include <cstdio>
#include <cstring>
//#include <cinttypes>
#include <algorithm>
using namespace std;
const int N=12;
typedef long long ll;
ll dp[2][1<<N];
int w, h;
int main(){
while (scanf("%d%d", &h, &w)&&w){
memset(dp, 0, sizeof dp);
if (w<h) swap(w,h);
int cur=0;
memset(dp,0,sizeof(dp));
dp[cur][0]=1;
for (int i=0;i<h;++i){
for (int j=0;j<w;++j){
cur^=1;
memset(dp[cur],0,sizeof(dp[cur]));
for (int st=0;st<(1<<w);++st){
if ((st&(1<<j))) dp[cur][st&(~(1<<j))]+=dp[cur^1][st];
if ((st&(1<<j))==0) dp[cur][st|(1<<j)]+=dp[cur^1][st];
if (j<w-1&&(st&(3<<j))==0) dp[cur][st|(1<<(j+1))]+=dp[cur^1][st];
}
}
}
printf("%lld\n", dp[(w*h)%2][0]);
}
return 0;
}
POJ1565 给定的矩阵中有一些数，我们可以选择一些数出来。现在规定不可以选择相邻的数（上下左右方向有公共边），问一次可以选的数的和最大为多少。
这题的转移方式和上一题“骨牌密铺”有点类似，同样使用轮廓线转移来写，记录的是轮廓线下方（注意是下方而不是下方和右方）方格是否可选的状态。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=21;
int a[N][N], dp[2][1<<N], n;
int main(){
while (scanf("%d", &n)!=EOF){
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 cur=0,pre=1;
dp[cur][0]=0;
int ans=0;
for (int i=0;i<n;++i){
for (int j=0;j<n;++j){
swap(cur,pre);
memset(dp[cur],0,sizeof(dp[cur]));
for (int st=0;st<(1<<n);++st){
dp[cur][st&(~(1<<j))]=dp[pre][st];
if ((st&(1<<j))==0&&(j==0||(st&(1<<(j-1)))==0)) {
dp[cur][st|(1<<j)]=dp[pre][st]+a[i][j];
}
}
for (int st=0;st<(1<<n);++st){
ans=max(ans,dp[cur][st]);
}
}
}
printf("%d\n", ans);
}
return 0;
}
POJ2167 与上题类似，不过这道题将“相邻”定义为周围八个格子。这时我们就不得不记录更多信息：对于宽度为n的图的轮廓线，我们将轮廓线下方和右方共n+1个方格是否可以选择的状态记录下来，并进行状态转移和计数。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=16;
int a[N][N], n, dp[2][1<<N];
int main(){
while (scanf("%d",&a[0][0])!=EOF){
char ch=0;
for (n=1;ch!='\n';++n){
scanf("%d%c",&a[0][n],&ch);
}
for (int i=1;i<n;++i){
for (int j=0;j<n;++j) scanf("%d",&a[i][j]);
}
// DP
memset(dp,0xff,sizeof(dp));
int cur=0,pre=1,ans=0;
dp[cur][0]=0;
for (int i=0;i<n;++i){
for (int j=0;j<n;++j){
swap(cur,pre);
memset(dp[cur],0xff,sizeof(dp[cur]));
//printf("[%d %d]\n", i,j);
for (int st=0;st<(2<<n);++st){
if (dp[pre][st]<0) continue;
//printf("%d: %d ", st, dp[pre][st]);
if(j<n-1){
dp[cur][st&(~(2<<j))]=
max(dp[cur][st&(~(2<<j))],dp[pre][st]);
if((st&(2<<j))==0){// ready to place
int nst=st|(7<<j);
nst=j>0?nst|(1<<(j-1)):nst;
nst&=((2<<n)-1);
dp[cur][nst]=max(dp[cur][nst],dp[pre][st]+a[i][j]);
}
}else{// next line
dp[cur][(st<<1)&((2<<n)-1)]=
max(dp[cur][(st<<1)&((2<<n)-1)],dp[pre][st]);
if((st&(2<<j))==0){// ready to place
dp[cur][(st<<1|(3<<j))&((2<<n)-1)]=
max(dp[pre][st]+a[i][j],dp[cur][(st<<1|(3<<j))&((2<<n)-1)]);
}
}
}
for (int st=0;st<(2<<n);++st)
if (dp[cur][st]>=0){
ans=max(ans,dp[cur][st]);
}
}
}
printf("%d\n", ans);
}
return 0;
}
未完待续
最小表示法
