题目链接

考虑状压DP，原本想的是一行行转移，而最后一行的状态需要记\(3^m\)个，然后直接转移的话，需要枚举该行的2变成0或1,以及0是否选入集合，又是一个\(3^m\)，复杂度爆炸，且难以优化状态。(原本还莽了一下，以为可以优化掉一些地方，然而全是2的数据就凉了。)

那么只能优化转移的方式了。所以这个时候应该改变一下传统的思路：并不是非得一次转移一行（这样枚举这行的情况是很浪费的）。对于一行，也可以按照行间DP那样的思路，直接从左往右一个个考虑，然后记录状态。问题在于要记录哪些状态，发现对于该行之前考虑过的位置，上一行的状态已经没用了，即只要记录下面轮廓线的状态即可。

对于同行之间的影响，我的做法是记录目前的0所在的那段是【没有关键点/按照有关键点考虑但目前还没有关键点/已有关键点】这三种状态，遇到一个1直接把第二种状态舍掉（非法）即可，效率\(O(3nm*3^m)\) ，（\(n,m\)其实可以更大一点）。

出错点：转移的时候，被转移的量一定要取min！！！

代码

#include
using namespace std;
const int N=10,M=10005;
int n,m,a[N][N],f[N][N][M][3],pw3[N];
int main()
{
	//freopen("1.in","r",stdin);
	//int t=11;
	//int s=3*t*t; for(int i=1;i<=t;i++) s*=3; cout<>n>>m;
	pw3[0]=1;
	for(int i=1;i<=m;i++) pw3[i]=pw3[i-1]*3;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char ch;
			scanf(" %c",&ch);
			a[i][j]=ch-'0';
		}
	}
	memset(f,0x3f,sizeof(f));
	f[1][0][0][0]=f[1][0][0][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int s=0;s