[luoguP1074] 靶形数独（搜索）

传送门

75分，太菜，不会优化了，吐了。

几点优化。

1.先搜索容易确定的位置

2.从中心往周围搜

3.枚举数字的时候倒序枚举

4.如果没有枚举到的数字都是最优情况的话也不能比当前ans大就剪枝

5.位运算

#include <cstdio> #include <iostream> #include <algorithm> #define max(x, y) ((x) > (y) ? (x) : (y)) #define tu(i, j) (((i) 1) / 3 * 3 + ((j) 1) / 3 + 1) int ans = 1, cnt; int hang[10], lie[10], jiu[10], shu[10], a[10][10], num[10][10], point[11]; struct node }p[101]; inline int read() inline bool cmp(node x, node y) inline int pd(int x, int y) inline bool check(int sum) return sum > ans; } inline void dfs(int x, int y, int k, int sum) for(int i = 9; i >= 1; i) if(!(hang[x] & (1 << i 1)) && !(lie[y] & (1 << i 1)) && !(jiu[tu(x, y)] & (1 << i 1))) } int main() } for(i = 1; i <= 9; i++) for(j = 1; j <= 9; j++) for(i = 1; i <= 9; i++) for(j = 1; j <= 9; j++) if(!a[i][j]) p[++cnt] = node(pd(i, j), i, j, num[i][j]); std::sort(p + 1, p + cnt + 1, cmp); dfs(p[1].x, p[1].y, 1, sum); printf("%d\n", ans); return 0; }

　　

上一篇：[luoguP1489] 猫狗大战（DP）

下一篇：[luoguP1273] 有线电视网（DP）

---

dfs