AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
ober02
,
2024-04-07 10:03:07
,
所有人可见
,
阅读 2
朴素做法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N;
long long f[N][M]; // 状态的数量
bool st[M]; // 记录 1 ~ 2^n - 1 是否 只有连续偶数个0
int main()
{
int n, m;
while(cin >> n >> m , n||m)
{
for(int i = 0 ; i < 1<<n ; i++){ // 预处理所有的st[i]
int cnt = 0; //记录当前连续0的数量
st[i] = true;
for(int j = 0 ; j < n; j++){ // 从第0位遍历至n-1位
if( (i >> j) & 1 ){ // 第j位为1
if(cnt & 1) st[i] = false; // 如果 cnt是奇数
cnt = 0;
}
else cnt++; // 第j位为0
}
if(cnt & 1) st[i] = false;
}
memset(f, 0 ,sizeof f); // 初始化为0
f[0][0] = 1; // 第0列没有伸出去第1列的,所以只有全是竖着的
for(int i = 1 ; i <= m ; i++) // 遍历 1到m列
{
for(int j = 0 ; j < 1<<n ; j++) //判断所有的f[i][j] 有多少 f[i-1][k] 可以到达
{
for(int k = 0; k < 1<<n ; k++){
if( (j&k) == 0 && st[j|k] ) f[i][j] += f[i-1][k]; //没有重复的1,且合并后只有偶数的连续0
}
}
}
cout << f[m][0] << endl; // ans
}
return 0;
}
优化做法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 12, M = 1 << N;
long long f[N][M]; // 状态的数量
bool st[M]; // 记录 1 ~ 2^n - 1 是否 只有连续偶数个0
vector<int> state[M]; //state[i] 中存储所有 k ,k -》i
int main()
{
int n, m;
while(cin >> n >> m , n||m)
{
for(int i = 0 ; i < 1<<n ; i++){ // 预处理所有的st[i]
int cnt = 0; //记录当前连续0的数量
st[i] = true;
for(int j = 0 ; j < n; j++){ // 从第0位遍历至n-1位
if( (i >> j) & 1 ){ // 第j位为1
if(cnt & 1) {// 如果 cnt是奇数
st[i] = false;
break;
}
cnt = 0;
}
else cnt++; // 第j位为0
}
if(cnt & 1) st[i] = false;
}
for(int i = 0 ; i < 1<<n ;i++)
{
state[i].clear();
for(int j = 0 ; j < 1<<n ;j++){
if( (j&i) == 0 && st[j|i] ) state[i].push_back(j);//没有重复的1,且合并后只有偶数的连续0
}
}
memset(f, 0 ,sizeof f); // 初始化为0
f[0][0] = 1; // 第0列没有伸出去第1列的,所以只有全是竖着的
for(int i = 1 ; i <= m ; i++) // 遍历 1到m列
{
for(int j = 0 ; j < 1<<n ; j++) //判断所有的f[i][j] 有多少 f[i-1][k] 可以到达
{
for(auto k:state[j]) f[i][j] += f[i-1][k];
}
}
cout << f[m][0] << endl; // ans
}
return 0;
}