POJ3254 Corn Fields 狀態壓縮DP

POJ3254 Corn Fields 狀態壓縮DP

感覺有些差不多，因為CF比賽狀壓被虐 所以開始刷刷題，從最簡單的開始復習吧，細節處理很差，唉

DP方程跟一般的有些不一樣，dp[i][j]表示在狀態i的情況下 到第j行的擺放有多少種，然後總數就是 dp[i][n - 1]求和，以第一行為邊界往下推，第一行邊界值為1，因為從第一行開始當前狀態當然就一種擺法了，可是原圖本身就有些地方能放不能放的，一開始放在一起處理了很煩弄不清楚了，後來看了別人的，先處理掉原圖的合法不合法，看來我太年輕，這樣接下來就很清晰了，當然題目說 每一行都不放也是一種狀態，一開始給看漏了，結果一直案例跑錯，還以為推錯了，看方程看了半年

#define MOD 100000000

int n,m,cnt;

int mp[15];
int aa[1<<15];
int dp[1<<15][15];

void init() {
	memset(mp,0,sizeof(mp));
	memset(dp,0,sizeof(dp));
	memset(aa,0,sizeof(aa));
}

bool input() {
	while(scanf(%d %d,&n,&m) == 2) {
		for(int i=0;i