（P2774 方格取数问题）<状压DP>

这是一道用状压DP似乎AC无望的题。。。 毕竟题解都是网络流。。。#># 不过用这个题学会了DP滚动数组的巧妙写法

题目描述

在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

输入输出格式

输入格式： 第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。

输出格式： 程序运行结束时，将取数的最大总和输出

输入输出样例

输入样例#1： 3 3 1 2 3 3 2 3 2 3 1 输出样例#1： 11

与“互不侵犯”不同的地方：

很明显的是，求的方向不同，所以DP方程不同，但其他方面的思想都基本一致。本题要把每种方案的结果算出来取最大值。初始化的一点小小的不同：每种方案对应的二进制数不仅要用于判断条件（无公共边），还有用于计算每种方案的代数和 while(t){ num[a][st]+=p[a][(t&1)*k];//k代表二进制的第k位，如移到第5位时，k为5 t>>=1; k++; } 滚动数组优化：注意到每一行的f都由上一行转移而来，所以可以用滚动数组。但是不能像背包问题那样无脑，因为无论你怎样调整循环的顺序，总是无法保证f数组依然保存上一行的结果。所以需要用另一个数组记录每一行DP完成后的值，下一行DP时调用这个数组里的值，而不是直接调用f。但是这样做需要每一行DP完成后将值赋到另一个数组里，复杂度高。一个比较巧妙的办法是，将f多开一维，新开的这一维只有0和1，代表每一行的准确值和计算值，即原来的f数组和新开的数组。每一次算完后，将0或1与1异或，这样0变成1，1变成0，实现两个数组的相互调用。

只有72分的代码

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n,m;//正整数 m 和 n，分别表示棋盘的行数和列数 int p[21][21]; int s[21][2000],num[2000][2000]; int st; long long f[2][2000]; void _state(){ for(int a=1;a<=m;++a){ st=0; for(int i=1;i<(1<<n);++i){ if(i&(i<<1)) { // cout<<a<<" "<<i<<endl; continue; } int t=i; int k=1; while(t){ num[a][st]+=p[a][(t&1)*k]; t>>=1; k++; } s[a][st++]=i; } } /* for(int i=0;i<=n;++i){ for(int j=0;j<=st;++j) cout<<num[i][j]<<"("<<s[i][j]<<")"<<" "; cout<<endl; }*/ } void DP(){ long long ans=0; int k=1,dm; // for(int i=1;i<st;++i) f[1][i]+=num[1][i]; for(int i=1;i<=m+5;++i){ dm=k^1; for(int a=0;a<=st;++a){ for(int b=0;b<=st;++b){ if(s[i][a]&s[i-1][b]) continue; f[dm][a]=max(f[k][b]+num[i][a],f[dm][a]); ans=max(ans,f[dm][a]); //f[k][a]=max(f[dm][a],f[k][a]);//这里不能赋值 } } k=dm; } printf("%lld",ans); } int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) scanf("%d",&p[i][j]); _state(); DP(); return 0; }