题解 P1879 【[USACO06NOV]玉米田Corn Fields】
一道状压dp
(我入门的第一题）
很久以前做的，现在回头看了一下，顺便写篇题解。
解题思路：以样例数据第一行为例，三个格子都可以放牧，即每个格子都可以选择放，或不放。再考虑附加条件“相邻格子不可同时放牧”，那么我们可以列出单看第一行时的所有可行状态如下（1代表放牧，0代表不放牧）
编号 状态
1 0 0 0
2 0 0 1
3 0 1 0
4 1 0 0
5 1 0 1
（表1）由此，可将表中的状态看作二进制表示，那么，只需将每种状态转化为相应的十进制数，即可只用一个数字，就能表示某一种状态，如下表：
编号 二进制 十进制
1 0 0 0 0
2 0 0 1 1
3 0 1 0 2
4 1 0 0 4
5 1 0 1 5
（表2）这种用一个数来表示一组数，以降低表示状态所需的维数的解题手段，就叫做状态压缩。
至此我们看到，在只考虑第一行的时候，有5种可行的放牧方案，但这只是我们要做的第一步。接下来要将第二行纳入考虑：
首先思考：纳入第二行后，会对当前问题造成什么样的影响？
答案还是那句话：“相邻格子不可同时放牧”！
也就是说，不止左右相邻不可以，上下之间也不能存在相邻的情况。
首先观察第二行，只有中间的格子可以放牧，那么我们的状态表格就可以相对简单些了～如下：
编号 二进制 十进制
1 0 0 0 0
2 0 1 0 2
（表3）只有两种可行状态，那么我们不妨一个一个来考察： 1、当第二行的状态为编号1时，第二行的三个格子都没有放牧，那么就不会与第一行的任何情况有冲突，第一行的5种方案都可行，即：第二行选用编号1的状态时，结合第一行，可得到5种可行的放牧方案；
2、当第二行的状态为编号2时，第二行中间的格子已经放牧了，那么第一行中间的格子就不可以放牧。看表2，发现其中第3种状态与当前第二行冲突，那么第一行只有4种方案是可行的，即：第二行选用编号2的状态时，结合第一行，可得到4种可行的放牧方案；
那么，在样例数据给出的情况下，我们的最终答案即为5+4=9；
贴原帖代码：
AC'sCode
#include <cstdio>
#include <cstring>
using namespace std;
#define mod 100000000
int M,N,top = 0;
//top表示每行最多的状态数
int state[600],num[110];
//state存放每行所有的可行状态（即没有相邻的状态
//
int dp[20][600];
//dp[i][j]:对于前i行数据，每行有前j种可能状态时的解
int cur[20];
//cur[i]表示的是第i行整行的情况
inline bool ok(int x){ //判断状态x是否可行
if(x&x<<1) return false;//若存在相邻两个格子都为1，则该状态不可行
return true;
}
void init(){ //遍历所有可能的状态
top = 0;
int total = 1 << N; //遍历状态的上界
for(int i = 0; i < total; ++i){
if(ok(i))state[++top] = i;
}
}
inline bool fit(int x,int k){ //判断状态x 与第k行的实际状态的逆是否有‘重合’
if(x&cur[k])return false; //若有重合，（即x不符合要求）
return true; //若没有，则可行
}
int main(){
while(scanf("%d%d",&M,&N)!= EOF){
init();
memset(dp,0,sizeof(dp));
for(int i = 1; i <= M; ++i){
cur[i] = 0;
int num;
for(int j = 1; j <= N; ++j){ //输入时就要按位来存储，cur[i]表示的是第i行整行的情况，每次改变该数字的二进制表示的一位
scanf("%d",&num); //表示第i行第j列的情况（0或1）
if(num == 0) //若该格为0
cur[i] +=(1<<(N-j)); //则将该位置为1（注意要以相反方式存储，即1表示不可放牧
}
}
for(int i = 1;i <= top;i++){
if(fit(state[i],1)){ //判断所有可能状态与第一行的实际状态的逆是否有重合
dp[1][i] = 1; //若第1行的状态与第i种可行状态吻合，则dp[1][i]记为1
}
}
/*
状态转移过程中，dp[i][k] =Sigma dp[i-1][j] （j为符合条件的所有状态）
*/
for(int i = 2; i <= M; ++i){ //i索引第2行到第M行
for(int k = 1; k <= top; ++k){ //该循环针对所有可能的状态，找出一组与第i行相符的state[k]
if(!fit(state[k],i))continue; //判断是否符合第i行实际情况
for(int j = 1; j <= top ;++j){ //找到state[k]后，再找一组与第i-1行符合，且与第i行（state[])不冲突的状态state[j]
if(!fit(state[j],i-1))continue; //判断是否符合第i-1行实际情况
if(state[k]&state[j])continue; //判断是否与第i行冲突
dp[i][k] = (dp[i][k] +dp[i-1][j])%mod; //若以上皆可通过，则将'j'累加到‘k'上
}
}
}
int ans = 0;
for(int i = 1; i <= top; ++i){ //累加最后一行所有可能状态的值
ans = (ans + dp[M][i])%mod;
}
printf("%d\n",ans);
}
}下面再贴一下我自己写的 （勿喷AC Code ）
/*#include<管理员真帅>*/
#include<bits/stdc++.h>
using namespace std;
const int modd=1e9;
int st[1<<13],mapp[1<<13];
int dp[13][1<<13];
bool judge1(int x)
{
return (x&(x<<1));
}
bool judge2(int i,int x)
{
return (mapp[i]&st[x]);
}
int main()
{
int n,m,x;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(st,0,sizeof(st));
memset(mapp,0,sizeof(mapp));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&x);
if(x==0)
{
mapp[i]+=(1<<(j-1));
}
}
}
int k=0;
for(int i=0;i<(1<<m);i++)
{
if(!judge1(i))
{
st[k++]=i;
}
}
for(int i=0;i<k;i++)
{
if(!judge2(1,i))
{
dp[1][i]=1;
}
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<k;j++)
{
if(judge2(i,j)) continue;
for(int f=0;f<k;f++)
{
if(judge2(i-1,f)) continue;
if(!(st[j]&st[f]))
dp[i][j]+=dp[i-1][f];
}
}
}
int ans=0;
for(int i=0;i<k;i++)
{
ans+=dp[n][i];
ans%=modd;
}
cout<<ans<<endl;
}
return 0;
}End.
(管理员哥哥真帅，能不能照顾一下我这个小蒟蒻鸭
（制作不易，求通过加赞鸭
(