题目连接： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2245
轮廓线DP 裸题
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxst = 1200; LL dp[2][maxst]; int main(){ int n,m; while(scanf("%d %d",&n,&m) != EOF){ if(n < m) swap(n,m); memset(dp,0,sizeof dp); dp[0][(1 << m) - 1] = 1; int cur_step = 0; for(int i = 0;i < n;++i){ for(int j = 0;j < m;++j){ cur_step = cur_step ^ 1; memset(dp[cur_step],0,sizeof dp[cur_step]); for(int st = 0;st < (1 << m);++st){ if( st & (1 << (m - 1)) ) dp[cur_step][(st << 1) ^ (1 << m)] += dp[1 - cur_step][st]; //上一步不放 if(i && !(st & (1 << (m - 1)))) dp[cur_step][(st << 1) ^ 1] += dp[1 - cur_step][st]; //竖着放 if(j && !(st & 1) && (st & (1 << (m - 1)))) dp[cur_step][(st << 1) ^ (1 << m) ^ 3] += dp[1 - cur_step][st];//横着放 } } } printf("%lld\n",dp[cur_step][(1 << m) - 1]); } }