补了一发轮廓线DP，发现完全没有必要从右往左设置状态，自然一点：
5 6 7 8 9
1 2 3 4
如此设置轮廓线标号，转移的时候直接把当前j位改成0或者1就行了。注意多记录些信息对简化代码是很有帮助的，尤其对于我这种代码经常错的一塌糊涂的人来说。。
呆马：
POJ 3254 Corn Fields
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define inf 1000000007
#define oo 100000000
#define maxn 15
#define maxm 5200 using namespace std; int n,m,mb;
int a[maxn][maxn];
int f[maxn][maxn][];
int bit[][maxn]; bool legal(int x, int y,int mask)
{
if (y==) if (bit[mask][y]&bit[mask][y+]) return ;
for (int i=;i<y-;i++) if (bit[mask][i]&bit[mask][i+]) return ;
for (int i=y;i<m;i++) if (bit[mask][i]&bit[mask][i+]) return ;
return ;
} int main()
{
scanf("%d%d",&n,&m);
memset(a,,sizeof(a));
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
scanf("%d",&a[i][j]);
mb=(<<m)-;
for (int mask=;mask<=mb;mask++)
{
int tmp=mask;
for (int i=;i<=m;i++)
{
bit[mask][i]=tmp%;
tmp/=;
}
}
memset(f,,sizeof(f));
f[][m][]=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
for (int mask=;mask<=mb;mask++)
if (legal(i,j,mask))
{
int tmp=<<(j-);
if (j==)
{
f[i][j][mask&(~tmp)]+=f[i-][m][mask];
f[i][j][mask&(~tmp)]%=oo;
if (!bit[mask][j] && a[i][j])
{
f[i][j][mask|tmp]+=f[i-][m][mask];
f[i][j][mask|tmp]%=oo;
}
}
else
{
f[i][j][mask&(~tmp)]+=f[i][j-][mask];
f[i][j][mask&(~tmp)]%=oo;
if (!bit[mask][j] && a[i][j])
{
f[i][j][mask|tmp]+=f[i][j-][mask];
f[i][j][mask|tmp]%=oo;
}
}
}
int ans=;
for (int mask=;mask<=mb;mask++)
if (legal(n+,,mask))
{
ans+=f[n][m][mask];
ans%=oo;
}
printf("%d\n",ans);
return ;
}
Corn Fields
BZOJ 1087 Kings
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define inf 1000000007
#define oo 100000000
#define maxn 11
#define maxm 1050 using namespace std; int n,m,mb;
long long f[maxn][maxn][][maxm];
int bit[maxm][maxn]; bool legal(int x, int y,int mask)
{
if (y==)
{
if (bit[mask][n]&bit[mask][n+]) return ;
if (bit[mask][n-]&bit[mask][n+]) return ;
}
else
{
if (bit[mask][y-]&bit[mask][n+]) return ;
if (bit[mask][y-]&bit[mask][n+]) return ;
}
for (int i=;i<n;i++) if (bit[mask][i]&bit[mask][i+]) return ;
return ;
} int main()
{
scanf("%d%d",&n,&m);
mb=(<<(n+))-;
memset(bit,,sizeof(bit));
for (int mask=;mask<=mb;mask++)
{
int tmp=mask;
for (int i=;i<=n+;i++)
{
bit[mask][i]=tmp%;
tmp/=;
}
}
memset(f,,sizeof(f));
f[][n][][]=;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
for (int k=;k<=m;k++)
for (int mask=;mask<=mb;mask++)
if (legal(i,j,mask))
{
int tmp=<<(j-);
int ost=mask&(~tmp),nst=mask|tmp;
if (((mask>>(j-))&)!=((mask>>n)&)) ost^=(<<n),nst^=(<<n);
if (j==)
{
f[i][j][k][ost]+=f[i-][n][k][mask];
if (k && !bit[mask][j] && !bit[mask][j+] && !bit[mask][j-])
f[i][j][k][nst]+=f[i-][n][k-][mask];
}
else
{
f[i][j][k][ost]+=f[i][j-][k][mask];
if (k && !bit[mask][j] && !bit[mask][j+] && !bit[mask][j-] && !bit[mask][n+])
f[i][j][k][nst]+=f[i][j-][k-][mask];
}
}
long long ans=;
for (int mask=;mask<=mb;mask++)
if (legal(n+,,mask))
{
ans+=f[n][n][m][mask];
}
printf("%lld\n",ans);
return ;
}
Kings