Mondriaan’s Dream
无优化
/*
f[i][j]:表示前i - 1列已经填好且第i列的状态为j
j表示第i - 1列是否出头
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N;
typedef long long LL;
int n, m;
LL f[N][M];
bool st[M];
int main() {
while (~scanf("%d%d", &n, &m)) {
if (n == 0 && m == 0)
break;
// 预处理st数组
for (int i = 0; i < 1 << n; i ++ ) {
int cnt = 0;
st[i] = true;
for (int j = 0; j < n; j ++ )
if (i >> j & 1) {
if (cnt & 1) {
st[i] = false;
cnt = 0;
}
} else
cnt ++ ;
if (cnt & 1)
st[i] = false;
}
// dp
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= m; i ++ )
for (int j = 0; j < 1 << n; j ++ )
for (int k = 0; k < 1 << n; k ++ )
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
printf("%lld\n", f[m][0]);
}
return 0;
}
优化
/*
f[i][j]:表示前i - 1列已经填好且第i列的状态为j
j表示第i - 1列是否出头
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 12, M = 1 << N;
typedef long long LL;
int n, m;
LL f[N][M];
bool st[M];
vector<vector<int>> v(M);
int main() {
while (~scanf("%d%d", &n, &m)) {
if (n == 0 && m == 0)
break;
// 预处理st数组(某列连续的空格数量是否为奇数)
for (int i = 0; i < 1 << n; i ++ ) {
int cnt = 0;
st[i] = true;
for (int j = 0; j < n; j ++ )
if (i >> j & 1) {
if (cnt & 1) {
st[i] = false;
cnt = 0;
break;
}
} else
cnt ++ ;
if (cnt & 1)
st[i] = false;
}
// 预处理_2(挑选出满足的相邻列的合法状态)
for (int i = 0; i < 1 << n; i ++ ) {
v[i].clear();
for (int j = 0; j < 1 << n; j ++ )
if ((i & j) == 0 && st[i | j])
v[i].push_back(j);
}
// dp
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= m; i ++ )
for (int j = 0; j < 1 << n; j ++ )
for (int k = 0; k < v[j].size(); k ++ )
f[i][j] += f[i - 1][v[j][k]];
printf("%lld\n", f[m][0]);
}
return 0;
}
Corn Fields
/*
f[i][j]:表示前i - 1行已经填好且第i行的状态为j的选法
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 13, M = 1 << N, mo = 100000000;
typedef long long LL;
int n, m;
LL f[N][M];
int st[N];
int check(int x, int y) {
if ((st[x] & y) != y)
return 0;
if ((y & (y << 1)) != 0)
return 0;
return 1;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
for (int i = 1; i <= n; i ++ ) {
st[i] = 0;
for (int j = 1; j <= m; j ++ ) {
int t;
scanf("%d", &t);
st[i] = (st[i] << 1) + t;
}
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < 1 << m; j ++ ) {
if (!check(i, j))
continue;
for (int k = 0; k < 1 << m; k ++ )
if ((j & k) == 0) {
f[i][j] += f[i - 1][k];
f[i][j] %= mo;
}
}
LL ans = 0;
for (int i = 0; i < 1 << m; i ++ ) {
ans += f[n][i];
ans %= mo;
}
printf("%lld\n", ans);
}
return 0;
}
Hie with the Pie
/*
f[i][j]:表示终点为i且当前状态为j的最小时间
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N, INF = 0x3f3f3f3f;
typedef long long LL;
int n;
LL f[N][M];
LL g[N][N];
void floyd() {
for (int k = 0; k <= n; k ++ )
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= n; j ++ )
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main() {
while (~scanf("%d", &n)) {
if (n == 0)
break;
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= n; j ++ )
if (i == j)
g[i][j] = 0;
else
g[i][j] = INF;
for (int i = 0; i <= n; i ++ )
for (int j = 0; j <= n; j ++ )
scanf("%lld", &g[i][j]);
floyd();
// dp
memset(f, 0x3f, sizeof f);
for (int i = 0; i <= n; i ++ )
f[i][1 << i] = g[0][i];
for (int j = 0; j < 1 << (n + 1); j ++ )
for (int i = 0; i <= n; i ++ )
for (int k = 0; k <= n; k ++ )
if ((j >> i) & 1)
f[i][j] = min(f[i][j], f[k][j & (~(1 << i))] + g[k][i]);
printf("%lld\n", f[0][(1 << (n + 1)) - 1]);
}
return 0;
}
炮兵阵地
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 15, P = 70;
int n, m;
int num; //仅是两个炮兵不互相攻击的条件下，符合条件的状态个数
int base[N];
int state[P];
int soldier[P]; //对应着，在state[i]状态下能放多少个士兵
int f[N][P][P];//f[i][j][k] 表示第i行状态为state[j]，第i-1行状态为state[k]时的最优解
char g[N][M];
int main() {
memset(base, 0, sizeof base);
memset(state, 0, sizeof state);
memset(soldier, 0, sizeof soldier);
memset(f, 0, sizeof f);
num = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) { //先初始化base
scanf("%s", g[i]);
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'H')
base[i] += 1 << j; //像0110000，这里计算为6
}
for (int i = 0; i < 1 << m; i++) { // 初始化soldier、state
if ( (i & (i << 1)) || (i & (i << 2)))
continue; // 出现了单行士兵两两攻击
int k = i;
while (k) {
soldier[num] += k & 1;
k >>= 1;
}
state[num ++ ] = i; //保存这个合法的状态
}
// dp
for (int i = 0; i < num; i ++ ) { //先初始化f[0][i][0]，即初始化第1行的情况
if (state[i] & base[0])
continue;
f[0][i][0] = soldier[i];
}
for (int r = 1; r < n; r ++ )
for (int i = 0; i < num; i ++ ) { //枚举第r行的状态
if (state[i] & base[r]) // 当前行合法
continue;
for (int j = 0; j < num; j++) { //枚举第r-1行的状态
if (state[j] & base[r - 1]) // 当前行合法
continue;
if (state[i] & state[j]) // r 和 r - 1 合法
continue;
for (int k = 0; k < num; k ++ ) { //枚举第r-2行的状态
if (state[k] & base[r - 2]) // 当前行合法
continue;
if (state[j] & state[k]) // r - 1 和 r - 2 合法
continue;
if (state[i] & state[k]) // r 和 r - 2 合法
continue;
f[r][i][j] = max(f[r][i][j], f[r - 1][j][k] + soldier[i]);
}
}
}
int ans = 0;
for (int i = 0; i < num; i ++ )
for (int j = 0; j < num; j ++ ) //枚举f[n-1][i][j]
ans = max(ans, f[n - 1][i][j]);
printf("%d\n", ans);
return 0;
}
