1棋盘式（基于连通性）
1 蒙德里安的梦想
#include<bits/stdc++.h> using namespace std; const int N=12,M=1<<11; vector<int> head;//用来记录第i层状态 vector<int> state[M];//用来记录第i层状态下的满足条件的i-1层的状态 bool st[M];//用来标记有没有连续个偶数0 long long f[N][M]; int n,m; bool check(int state)//用来处理一个数有没有偶数个0 { int cnt=0; for(int i=0;i<n;i++) if(state>>i&1) { if(cnt&1) return false; cnt=0; } else cnt++; if(cnt&1) return false; return true; } int main() { while(cin>>n>>m,n||m) { memset(f,0,sizeof f);//刷新下一层状态 head.resize(0);//刷新下一层状态 for(int i=0;i<1<<n;i++)//求一个数有没有连续偶数个0 st[i]=check(i); for(int j=0;j<1<<n;j++)//枚举第i层状态 { state[j].resize(0);//刷新下一层状态 bool flag=false;//用来标记这个数合不合法 for(int k=0;k<1<<n;k++)//枚举第i-1层状态 if((j&k)==0&&st[j|k])//假如有连续偶数个0和j和k不冲突 { flag=true; state[j].push_back(k);//则把这个合法状态放进j中 } if(flag) head.push_back(j);//假如当前第i个符合转移，则放进i里 } //前面是预处理，为下面的dp做铺垫 f[0][0]=1;//前0个状态一个没放也是个合法状态 for(int i=1;i<=m;i++)//枚举每一列 for(int j:head)//枚举第j列的状态 for(int k:state[j])//枚举该状态下可转移的数 f[i][j]+=f[i-1][k]; cout<<f[m][0]<<endl;//输出第m列突出来的数0个也就是状态为0的情况 } return 0; }
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=12,M=1<<10,K=110; vector<int> state;//用来记录没有连续个1的数的合法状态 int cnt[M];//用来记录i这个数的国王数量 ll f[N][K][M]; vector<int> head[M];//记录第i行的合法转移方案 int n,m; bool check(int state)//用来判断有没有连续个1 { for(int i=0;i<n;i++) if((state>>i&1)&&(state>>i+1&1)) return false; return true; } int count(int state)//用来求1的数量，也就是国王的数量 { int res=0; for(int i=0;i<n;i++) if(state>>i&1) res++; return res; } int main() { cin>>n>>m; for(int i=0;i<1<<n;i++)//用来求一行有没有连续个1 if(check(i))//假如没有说明合法 { state.push_back(i);//把他放进状态里 cnt[i]=count(i);//在记录一下该合法状态下国王的数量，也就是1的个数 } for(int i=0;i<state.size();i++)//用来求连续第i行和第i-1行不能互相攻击到的状态 for(int j=0;j<state.size();j++) { int a=state[i],b=state[j]; if((a&b)==0&&check(a|b))//假如不能互相攻击到 head[i].push_back(j);//则第i行的状态可以转移到j,该行可以转移的放进该行中 } //前面是预处理，为下面的dp做铺垫 f[0][0][0]=1;//这也是一个合法方案，则初始化为1 for(int i=1;i<=n+1;i++)//枚举每一行，这里可以枚举多一行，待会求数量就直接f[n+1][m][0]就行 for(int j=0;j<=m;j++)//枚举国王的数量 for(int a=0;a<state.size();a++)//枚举该行的状态 for(auto b:head[a])//枚举改行合法可以转移的上一行状态 { int c=cnt[state[a]]; if(c<=j)//假如国王数量小于当前国王数量 f[i][j][a]+=f[i-1][j-c][b];//则可以转移 } cout<<f[n+1][m][0]<<endl;//输出前n+1行国王数为m且该行状态为0，也就是第n+1行没任何操作，也即总数量 return 0; }
3 玉米田（十字形）
#include<bits/stdc++.h> using namespace std; const int N=14,M=1<<12,mod=1e8; vector<int> state;//用来记录没有连续个1的数的合法状态 vector<int> head[M];//记录第i行的合法转移方案 int f[N][M]; int g[N];//用来存每一行的不肥沃的地，也就是让不肥沃为1 int n,m; bool check(int state)//用来判断有没有连续个1 { for(int i=0;i<m;i++) if((state>>i&1)&&(state>>i+1&1)) return false; return true; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=0;j<m;j++) { int a; cin>>a; if(!a) g[i]+=1<<j;//假如是不肥沃的地，则把该列的1加到该行中 } for(int i=0;i<1<<m;i++)//用来求一行有没有连续个1 if(check(i))//假如没有说明合法 state.push_back(i);//把他放进状态里 for(int i=0;i<state.size();i++)//用来求连续第i行和第i-1行不能互相攻击到的状态 for(int j=0;j<state.size();j++) { int a=state[i],b=state[j]; if((a&b)==0)//假如上下两行不相邻 head[i].push_back(j);//则第i行的状态可以转移到j,该行可以转移的放进该行中 } //前面是预处理，为下面的dp做铺垫 f[0][0]=1;//不种也是个合法方案 for(int i=1;i<=n+1;i++)//枚举每一行，这里可以枚举多一行，待会求数量就直接f[n+1][0]就行 for(int a=0;a<state.size();a++)//枚举该行的状态 if((g[i]&state[a])==0)//假如该行的状态与不肥沃的土地不冲突 for(int b:head[a])//枚举改行合法可以转移的上一行状态 f[i][a]=(f[i][a]+f[i-1][b])%mod;//进行转移 cout<<f[n+1][0]<<endl;//输出前n+1行的地且，i+1行的状态是0，也就是不进行操作的数量，也即总数量 return 0; }
4 炮兵阵地（十字形2）
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=110,M=1<<10; vector<int> state;//用来记录三个连续位置的数中最多只有一个1的数的合法状态 int f[2][M][M]; int g[N];//用来存每一行的山地，也就是让山地为1 int cnt[M];//用来存合法数中1的个数 int n,m; bool check(int state)//用来判断三个连续位置的数中最多只有一个1的数的合法状态 { for(int i=0;i<m;i++) if((state>>i&1)&&((state>>i+1&1)||(state>>i+2&1))) return false; return true; } int count(int state)//用来算一个数中1的个数 { int res=0; for(int i=0;i<m;i++) if(state>>i&1) res++; return res; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=0;j<m;j++) { char a; cin>>a; if(a=='H') g[i]+=1<<j;//假如是山地，则把该列的1加到该行中 } for(int i=0;i<1<<m;i++)//用来求三个连续位置的数中最多只有一个1的数 if(check(i))//假如合法 { state.push_back(i);//把他放进状态里 cnt[i]=count(i);//并记录该数1的个数 } //前面是预处理，为下面的dp做铺垫 for(int u=1;u<=n+2;u++)//枚举每一行 for(int i=0;i<state.size();i++)//枚举第i-1行的状态 for(int j=0;j<state.size();j++)//枚举第i行的状态 { int a=state[i],b=state[j];//a是第i-1行状态,b是第i行状态 if((g[u-1]&a|g[u]&b)) continue;//假如i和i-1都放在了山地，则不合法 //反之合法 for(int k=0;k<state.size();k++)//枚举第i-2行的状态 { int c=state[k];//c是第i-2行状态 if((a&b)|(a&c)|(b&c)) continue; //假如三行有一列同时有1，则不合法 f[u&1][i][j]=max(f[u-1&1][k][i]+cnt[b],f[u&1][i][j]);//则进行状态转移 } } cout<<f[n+2&1][0][0]<<endl;//输出前n+2行且,n+1行的状态是0，n+2行也就是不进行操作的最大值 return 0; }
2 集合式
1 愤怒的小鸟
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; #define x first #define y second #define db double const int N=20,M=1<<18; const db eps=1e-6; typedef pair<db,db> pdd; int f[M]; pdd q[N]; int n,m; int path[N][N];/ bool cmp(db x,db y)//因为浮点数会失精度，用来判断两个数是否相等 { if(fabs(x-y)<eps) return true; return false; } int main() { int T; cin>>T; while(T--) { cin>>n>>m; for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y; memset(path,0,sizeof path);//清空上一维的状态 for(int i=0;i<n;i++) { path[i][i]=1<<i;//自己与自己的抛物线能打自己，避免有时候只有一个点占一条抛物线 for(int j=0;j<n;j++) { db x1=q[i].x,y1=q[i].y; db x2=q[j].x,y2=q[j].y; if(cmp(x1,x2)) continue;//判断相不相等，假如相等这条抛物线不存在 db a=(y1/x1-y2/x2)/(x1-x2),b=y1/x1-a*x1; if(a>0||cmp(a,0.0)) continue;//开口向下，所以a<0 for(int k=0;k<n;k++)//枚举这条抛物线能打到的其他点 { db x=q[k].x,y=q[k].y; if(cmp(a*x*x+b*x,y)) path[i][j]+=1<<k;//假如这个点在抛物线上，则加到这个ij点的状态下 } } } memset(f,0x3f,sizeof f);//清空上一维的数，因为要最小值，所以初始化为正无穷 f[0]=0;//这也是个合法的状态，初始化为0 for(int i=0;i<1<<n;i++)//枚举每一个状态 { int x=0; for(int j=0;j<n;j++)//找这个状态中没有猪的位置，也就是0的位置 if(!(i>>j&1)) { x=j; break; } for(int j=0;j<n;j++)//更新一下这个状态i与这只猪的状态下的最小值 f[i|path[x][j]]=min(f[i|path[x][j]],f[i]+1); } cout<<f[(1<<n)-1]<<endl;//输出所有猪打完的最小值，也就是所有位置都是1的状态 } return 0; }
