样例
转移状态写法
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N=12,M=1<<N;
LL f[N][N*N][M],cnt[M];
// f[i][j][k]:
// 已经摆好了前i行且摆好了j个棋子状态为k时的合法方案数
vector<LL> state;
vector<LL> head[M];
int n,m;
//检查是否存在两个连续的一
bool check(int u){
for(int i=0;i<n;i++){
if((u>>i&1)&&(u>>i+1&1)){
return false;
}
}
return true;
}
//统计该状态中1数量的个数
int count(int u){
int cnt=0;
for(int i=0;i<n;i++){
if(u>>i&1){
cnt++;
}
}
return cnt;
}
int main(){
ios::sync_with_stdio,cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<1<<n;i++){
if(check(i)){
state.push_back(i);
cnt[i]=count(i);
}
}
//统计state[i]这一合法状态可由谁转移过来
for(int i=0;i<state.size();i++){
for(int j=0;j<state.size();j++){
int a=state[i],b=state[j];
//如果ab没有同一位同时为一的数也没有相邻位为一的数
//那么ab状态可互相转移
if((a&b)==0&&check(a|b)){
head[a].push_back(b);
}
}
}
//dp:
f[0][0][0]=1;
for(int i=1;i<=n+1;i++){
for(int j=0;j<=m;j++){
for(int a=0;a<state.size();a++){
for(auto b:head[state[a]]){
if(j>=cnt[state[a]]){
f[i][j][state[a]]+=f[i-1][j-cnt[state[a]]][b];
}
}
}
}
}
cout<<f[n+1][m][0];
return 0;
}
转移下标写法
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N=12,M=1<<N;
LL f[N][N*N][M],cnt[M];
// f[i][j][k]:
// 已经摆好了前i行且摆好了j个棋子状态下标为k时的合法方案数
vector<LL> state;
vector<LL> head[M];
int n,m;
//检查是否存在两个连续的一
bool check(int u){
for(int i=0;i<n;i++){
if((u>>i&1)&&(u>>i+1&1)){
return false;
}
}
return true;
}
//统计该状态中1数量的个数
int count(int u){
int cnt=0;
for(int i=0;i<n;i++){
if(u>>i&1){
cnt++;
}
}
return cnt;
}
int main(){
ios::sync_with_stdio,cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=0;i<1<<n;i++){
if(check(i)){
state.push_back(i);
cnt[i]=count(i);
}
}
//统计state[i]这一合法状态可由谁转移过来
for(int i=0;i<state.size();i++){
for(int j=0;j<state.size();j++){
int a=state[i],b=state[j];
//如果ab没有同一位同时为一的数也没有相邻位为一的数
//那么ab状态可互相转移
if((a&b)==0&&check(a|b)){
head[i].push_back(j);
}
}
}
//dp:
f[0][0][0]=1;
for(int i=1;i<=n+1;i++){
for(int j=0;j<=m;j++){
for(int a=0;a<state.size();a++){
for(auto b:head[a]){
if(j>=cnt[state[a]]){
f[i][j][a]+=f[i-1][j-cnt[state[a]]][b];
}
}
}
}
}
cout<<f[n+1][m][0];
return 0;
}