插头dp [入土]

题目链接

西江月·证明

即得易见平凡，仿照上例显然。

留作习题答案略，读者自证不难。

反之亦然同理，推论自然成立。

略去过程QED，由上可知证毕

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
long long dp[11][2048];
int w, h;

bool TFL(int ovo){
	int i = 0;
	while(i < w){
		if(ovo & (0x1 << i)){
			if(i == w - 1 or (ovo & (0x1 << (i + 1))) == 0) return 0;
			i += 2;
		}else i ++;
	}return 1;
}

bool CT(int sa, int sb){//判断状态(i, sa)和(i-1, sb)是否兼容.(兼容性测试
	int i = 0;
	while(i < w){
		if((sa & (0x1 << i)) == 0){
			if((sb & (0x1 << i)) == 0) return 0;
			i ++;
		}
		else{
			if((sb & (0x1 << i)) == 0) i ++;
			else if((i == w - 1) or !((sa & (0x1 << (i + 1))) and (sb & (0x1 << (i + 1))))) return 0;
			else i += 2;
		}
	}
	return 1;
}

int main(){
	while(1){
		cin >> h >> w;
		if(h == 0 and w == 0) break;
		if(w > h) swap(w, h); //H是大的 W是小的
		int ovo = 2 << (w - 1);
		memset(dp, 0, sizeof(dp));
		for(int j = 0; j < ovo; j++) if(TFL(j)) dp[0][j] = 1;
		for(int i = 1; i < h; i ++)
		  for(int j = 0; j < ovo; j ++) // iterate all status for line i
		    for(int k = 0; k < ovo; k ++) // iterate all status for line i-1
		      if(CT(j, k)) dp[i][j] += dp[i - 1][k];
		printf("%lld
", dp[h - 1][ovo - 1]);
	}
	return 0;
}

QED