https://vjudge.net/problem/UVA-11270
题意：
用1×2骨牌覆盖n×m棋牌，有多少种方法？
思路：
这道题目是典型的轮廓线DP题。
所谓轮廓线DP，就是以整行整列为状态进行动态规划时无法进行状态转移，那么此时就可以用到轮廓线，当然，这种方法只能使用在一个窄棋盘上，大了肯定是不行的，要超时！
'
轮廓线DP就是按照从上到下，从左到右的顺序进行状态转移，每个格子用二进制来表示状态，1代表的就是覆盖，0代表未覆盖。
以本题为例，如上图，我们现在要计算 k 格子，那么与它有关的就是k4 k3 k2 k1 k0这5个格子。
现在，我们对于每个格子都有三种决策：
1、不放
不放的条件是其上面的格子必须是1（也就是k4必须是1），否则无法覆盖所有的棋盘的。
如果满足条件，那么就进行状态转移，d[cur][新状态]+=d[1-cur][旧状态]，也就是d[cur][k3k2k1k0k]+=d[1-cur][k4k3k2k1k0]。
2、上放
上放的条件是其上面的格子必须是0。
3、左放
左放的条件其左边的格子必须是0。
具体的算法实现请参见代码。
注意：这道题目数组开小点，开到1<<15会TLE，11就可以了！！
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn=11;
int n,m;
int cur;
ll d[2][1<<maxn];
void update(int a,int b) //a是m位的旧状态,b是m+1位的新状态
{
if(b&(1<<m)) d[cur][b^(1<<m)]+=d[1-cur][a]; //先检查新状态的轮廓线首是否为1，是1则更新状态
} //因为轮廓线首位1，所以b^(1<<m)就是将首位置为0，将新状态变成m位
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
if(n<m) swap(n,m);
memset(d,0,sizeof(d));
d[0][(1<<m)-1]=1;
cur=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cur^=1;
memset(d[cur],0,sizeof(d[cur]));
for(int k=0;k < (1<<m);k++)
{
update(k,k<<1); //不放，直接将二进制左移一位形成新状态
if(i && !(k&(1<<m-1))) update(k,(k<<1)^(1<<m)^1); //上放，要求轮廓线首为0且为非首行
if(j && !(k&1)) update(k,(k<<1)^3); //左放，要求轮廓线首为1，尾为0，且为非首列
}
}
}
printf("%lld
",d[cur][(1<<m)-1]);
}
return 0;
}