InputThe input consists of several test cases. The first line of the input is the number of the cases. There are no more than 10 cases.
For each case, the first line contains the integer numbers N and M, 1<=N, M<=11. Each of the next N lines contains M numbers (either 0 or 1) separated by a space. Number 0 means a cell which has no trees and number 1 means a cell that has exactly one tree.
OutputFor each case, you should print the desired number of ways in one line. It is guaranteed, that it does not exceed 2 63 ?C 1. Use the format in the sample.Sample Input
2 6 3 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 2 4 1 1 1 1 1 1 1 1
Sample Output
Case 1: There are 3 ways to eat the trees. Case 2: There are 2 ways to eat the trees.
插头DP
累得很，想着快点A了去睡觉，结果真的没怎么调就A了
果然休息是人最大的动力吗233
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define LL long long 6 using namespace std; 7 const int mxn=15; 8 int read(){ 9 int x=0,f=1;char ch=getchar(); 10 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 11 while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();} 12 return x*f; 13 } 14 int mp[mxn][mxn]; 15 LL f[2][1<<13]; 16 LL tmp[1<<13]; 17 int n,m; 18 int main(){ 19 int i,j,cas=0; 20 int T=read(); 21 while(T--){ 22 memset(f,0,sizeof f); 23 n=read();m=read(); 24 for(i=1;i<=n;i++) 25 for(j=1;j<=m;j++) 26 mp[i][j]=read(); 27 int ed=(1<<(m+1)); 28 int now=0,pre=1; 29 f[now][0]=1; 30 for(i=1;i<=n;i++){ 31 for(j=ed-1;j>=0;j--)tmp[j]=f[now][j]; 32 memset(f[now],0,sizeof f[now]); 33 for(j=ed-1;j>=0;j--)f[now][j<<1]=tmp[j]; 34 // for(j=0;j<(ed>>1);j++)f[now][j<<1]=f[now][j]; 35 for(j=1;j<=m;j++){ 36 swap(now,pre); 37 memset(f[now],0,sizeof f[now]); 38 for(int k=0;k<ed;k++){ 39 // printf("k:%d w:%I64d ",k,f[pre][k]); 40 int x=k&(1<<(j-1)); 41 int y=k&(1<<j); 42 if(mp[i][j]){ 43 if(x && y){//11 -> 00 44 f[now][k^(1<<(j-1))^(1<<j)]+=f[pre][k]; 45 } 46 else if(x && !y){//10 -> 01 10 47 f[now][k]+=f[pre][k]; 48 f[now][k^(1<<(j-1))^(1<<j)]+=f[pre][k]; 49 } 50 else if(!x && y){//01 -> 01 10 51 f[now][k]+=f[pre][k]; 52 f[now][k^(1<<(j-1))^(1<<j)]+=f[pre][k]; 53 } 54 else if(!x && !y){//00 -> 11 55 f[now][k^(1<<(j-1))^(1<<j)]+=f[pre][k]; 56 } 57 } 58 else{ 59 if(!x && !y)f[now][k]=f[pre][k]; 60 } 61 } 62 // printf("%d %d:%I64d\n",i,j,f[now][0]); 63 } 64 } 65 printf("Case %d: There are %I64d ways to eat the trees.\n",++cas,f[now][0]); 66 } 67 return 0; 68 }
原文：http://www.cnblogs.com/SilverNebula/p/6442411.html