3 条题解
-
0
摆上马
80 分
#include <bits/stdc++.h> using namespace std; const int MOD = 1'000'000'000 + 7; int x, y; // dp[i][sta1][sta2] 前i行，第i行摆放方案为 sta1，第i-1行摆放方案为 sta2，的摆放方案数 int dp[105][(1 << 6) - 1 + 5][(1 << 6) - 1 + 5]; // 检查相邻两行是否有冲突 bool check1(int sta1, int sta2) { for (int i = 0; i <= y - 1; i++) // 枚举sta1的每个1 { if ((sta1 & (1 << i)) == 0) continue; for (int j = 0; j <= y - 1; j++) { if ((sta2 & (1 << j)) == 0) continue; // sta1 的 i 的位置有马、sta2 的 j 的位置有马 if (j == i + 2) { // sta2 xxjxxxx // sta1 xxxxixx if ((sta1 & (1 << i + 1)) && (sta2 & (1 << j - 1))) continue; return true; } if (j == i - 2) { // sta2 xxxxxxjxx // sta1 xxxxixxxx if ((sta1 & (1 << i - 1)) && (sta2 & (1 << j + 1))) continue; return true; } } } return false; } // 检查间隔一行的两行有没有冲突 bool check2(int sta1, int sta2, int sta3) { for (int i = 0; i <= y - 1; i++) // 枚举sta1的每个1 { if ((sta1 & (1 << i)) == 0) continue; for (int j = 0; j <= y - 1; j++) { if ((sta3 & (1 << j)) == 0) continue; // sta1 的 i 的位置有马、sta3 的 j 的位置有马 if (j == i + 1 || j == i - 1) { if ((sta2 & (1 << i)) && (sta2 & (1 << j))) continue; return true; } } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> x >> y; memset(dp, 0, sizeof(dp)); // 处理边界情况 前0行，啥都不摆的时候是一种合法方案 dp[0][0][0] = 1; int ans = 0; for (int i = 1; i <= x; i++) { // 第i行 for (int sta1 = 0; sta1 <= (1 << y) - 1; sta1++) { // 第i-1行 for (int sta2 = 0; sta2 <= (1 << y) - 1; sta2++) { if (check1(sta1, sta2)) continue; // 求 dp[i][sta1][sta2] // 枚举上上行（i-2）的状态 for (int sta3 = 0; sta3 <= (1 << y) - 1; sta3++) { if (check1(sta2, sta3)) continue; if (check2(sta1, sta2, sta3)) continue; dp[i][sta1][sta2] += dp[i - 1][sta2][sta3]; dp[i][sta1][sta2] %= MOD; } if (i == x) { ans += dp[i][sta1][sta2]; ans %= MOD; } } } } cout << ans << "\n"; return 0; }100分
#include <bits/stdc++.h> using namespace std; const int MOD = 1'000'000'000 + 7; int x, y; // dp[i][sta1][sta2] 前i行，第i行摆放方案为 sta1，第i-1行摆放方案为 sta2，的摆放方案数 int now, pre; // 当前是第now行，上一行是第 pre 行 int dp[2][(1 << 6) - 1 + 5][(1 << 6) - 1 + 5]; // 检查相邻两行是否有冲突 bool check1(int sta1, int sta2) { for (int i = 0; i <= y - 1; i++) // 枚举sta1的每个1 { if ((sta1 & (1 << i)) == 0) continue; for (int j = 0; j <= y - 1; j++) { if ((sta2 & (1 << j)) == 0) continue; // sta1 的 i 的位置有马、sta2 的 j 的位置有马 if (j == i + 2) { // sta2 xxjxxxx // sta1 xxxxixx if ((sta1 & (1 << i + 1)) && (sta2 & (1 << j - 1))) continue; return true; } if (j == i - 2) { // sta2 xxxxxxjxx // sta1 xxxxixxxx if ((sta1 & (1 << i - 1)) && (sta2 & (1 << j + 1))) continue; return true; } } } return false; } // 检查间隔一行的两行有没有冲突 bool check2(int sta1, int sta2, int sta3) { for (int i = 0; i <= y - 1; i++) // 枚举sta1的每个1 { if ((sta1 & (1 << i)) == 0) continue; for (int j = 0; j <= y - 1; j++) { if ((sta3 & (1 << j)) == 0) continue; // sta1 的 i 的位置有马、sta3 的 j 的位置有马 if (j == i + 1 || j == i - 1) { if ((sta2 & (1 << i)) && (sta2 & (1 << j))) continue; return true; } } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> x >> y; memset(dp, 0, sizeof(dp)); // 处理边界情况 前0行，啥都不摆的时候是一种合法方案 dp[0][0][0] = 1; pre = 0; now = 1; int ans = 0; for (int i = 1; i <= x; i++) { // 第i行 for (int sta1 = 0; sta1 <= (1 << y) - 1; sta1++) { // 第i-1行 for (int sta2 = 0; sta2 <= (1 << y) - 1; sta2++) { dp[now][sta1][sta2] = 0; if (check1(sta1, sta2)) continue; // 求 dp[i][sta1][sta2] // 枚举上上行（i-2）的状态 for (int sta3 = 0; sta3 <= (1 << y) - 1; sta3++) { if (check1(sta2, sta3)) continue; if (check2(sta1, sta2, sta3)) continue; dp[now][sta1][sta2] += dp[pre][sta2][sta3]; dp[now][sta1][sta2] %= MOD; } if (i == x) { ans += dp[now][sta1][sta2]; ans %= MOD; } } } now = 1 - now; pre = 1 - pre; } cout << ans << "\n"; return 0; } -
0
33DAI LV 5 (1/1) @ 2023-1-14 16:33:46
售货员的难题
#include <bits/stdc++.h> using namespace std; int n; // n个村庄，编号分别为 0~n-1，商店在 0 int len[25][25]; // len[i][j] i->j 的距离 // dp[sta][i] 已经走过了sta这些村庄，并且最终走到的是 sta 中的 i 村庄的最短路程 int dp[(1 << 20) - 1 + 5][25]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i <= n - 1; i++) for (int j = 0; j <= n - 1; j++) cin >> len[i][j]; // dp memset(dp, 0x3f, sizeof(dp)); // 全都设置为 MAX_INT/2 左右 for (int sta = 0; sta <= (1 << n) - 1; sta++) { for (int i = 0; i <= n - 1; i++) { // 如果已经走过的位置里面没有i，说明当前方案不合法 if ((sta & (1 << i)) == 0) continue; // 如果当前只走过了一个村庄 if (sta == (1 << i)) { // 如果是商店就行，否则方案就是不合法的 if (i == 0) dp[sta][i] = 0; } // 枚举上一个村庄走了谁 for (int j = 0; j <= n - 1; j++) { if ((sta & (1 << j)) == 0 || i == j) continue; dp[sta][i] = min(dp[sta][i], dp[sta - (1 << i)][j] + len[j][i]); } } } // 找到答案 int ans = 0x3f3f3f3f; for (int i = 1; i <= n - 1; i++) // 不能以商店（0号点）结束 ans = min(ans, dp[(1 << n) - 1][i] + len[i][0]); cout << ans << "\n"; return 0; } -
0
互不侵犯
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 9; // MAXN int n, k; // dp[i][j][sta] 前i行放j个国王，第i行的摆放方法为 sta，有多少种方案 int dp[N + 5][N * N + 5][(1 << 9) - 1 + 5]; int lowbit(int x) { return x & (-x); } int cnt1(int x) { int res = 0; while (x > 0) { res++; x -= lowbit(x); } return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; dp[0][0][0] = 1; int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { for (int sta = 0; sta <= (1 << n) - 1; sta++) { // 计算 dp[i][j][sta] // sta不合法就排除掉 if (sta & (sta << 1)) continue; // 国王用多了就排除掉 if (cnt1(sta) > j) continue; // 枚举前一行的情况 for (int psta = 0; psta <= (1 << n) - 1; psta++) { // psta 自身合法 if (psta & (psta << 1)) continue; // sta 与 psta 是否冲突 if (sta & psta) continue; if (sta & (psta << 1)) continue; if (sta & (psta >> 1)) continue; dp[i][j][sta] += dp[i - 1][j - cnt1(sta)][psta]; } if (i == n && j == k) ans += dp[i][j][sta]; } } } cout << ans << "\n"; return 0; }
- 1