…
Note :
1. 对于这个搜索题，考察搜索的顺序的调整，在之前比赛的时候，我一直希望可以提前搜索到答案，以尽可能早的完成剪枝，但是实际运行时这样写一直TLE，更好的安排顺序是先搜索那些限制多的位置。
2. 实际中，要做到实时的维护限制位置，代价太大，但是在预处理阶段，找到一组近似的顺序还是可以做到的。
3. 在搜索部分的代码里第四行的部分…
...
void dfs(int step){
if (step == up) ans = max(ans, bonus);
else {
int x = P[step].x, y = P[step].y;
int q = m - (c[x]|r[y]|s[x/3][y/3]), p;
while (q!=0){
p = q & -q; q -= p;
c[x] |= p; r[y] |= p; s[x/3][y/3] |= p; bonus += l[p]*w[x][y]; dfs(step + 1);
c[x] &=~p; r[y] &=~p; s[x/3][y/3] &=~p; bonus -= l[p]*w[x][y];
}
}
}
...
我定义了一个x, y 作为辅助变量，（开始的想法只是少打许多字符，代码格式好看许多），我猜想这个可能会增加堆栈体积，因此在后面写的时候把它去掉，（但是代码反而速度变慢许多（0.5s 左右），具体原因不明。）#
4. 下面的代码是自我感觉比较理想的一份，希望同时兼顾搜索树限制以及最优剪枝，但是经过测试最快的代码（1.36s）是把所有最优剪枝的部分完全剔除掉后的（因此这份代码放在前面）。第二一份则是只可以做到 2.00s 左右的样子。
int c[9], r[9], s[3][3];
这三组变量是用位运算记录限制的位置，
column[9] 记录横行的限制， row[9] 记录纵列的限制。
sub-square[3][3] 则是记录每个子正方形，因为牵涉到模运算，这个部分数组从 0 开始开会更方便。
int a[9][9], w[9][9], l[9];
a 数组用于记录每个初始化时格子里填的数字。（当然其实在后面的代码里也用不到，去掉也可。）
…
w 数组用于记录每个格子的权值，它和 l 数组（一个在位操作的会用到的辅助数组，具体做什么的自己读代码啦#）一样，是在整个程序开始读数据之前先预处理好的，之后也都作为常量存在。
其它则没有什么要说的了，哦还有 t 数组用来记录每个格子被限制的数值，每次取出一个被限制数字最大的一个，对那些已经有数字的格子，则赋值为 – INF。
#include
#include
using namespace std;
const int INF = 1000;
const int m = (1<<9)-1;
int c[9], r[9], s[3][3], l[m];
int a[9][9], w[9][9], t[9][9];
int bonus, ans, up;
struct po{
int x, y;
} P[9*9];
void label(int x, int y){
for (int i=0;i<9;i++){
t[i][y]++; t[x][i]++;
}
int i0 = x/3 * 3, j0 = y/3 * 3;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
t[i0+i][j0+j]++;
}
void init(){
for (int i=0;i<9;i++)
for (int j=0;j<9;j++)
w[i][j] = 10 - max(abs(i-4), abs(j-4));
for (int i=1,p=1;i<=9;i++,p<<=1)
l[p] = i;
}
void load(){
memset(c, 0, sizeof(c)); memset(r, 0, sizeof(r)); memset(s, 0, sizeof(s));
memset(t, 0, sizeof(t)); bonus = 0; up = 9*9; ans = -1;
int i, j, k;
for (i=0,k=0;i<9;i++)
for (j=0;j<9;j++,k++){
scanf("%d", &a[i][j]); P[k].x = i; P[k].y = j;
if (a[i][j]!=0){
int p = (1<<(a[i][j]-1));
c[i] |= p; r[j] |= p; s[i/3][j/3] |= p;
bonus += a[i][j]*w[i][j]; t[i][j] = -INF;
label(i, j);
up--;
}
}
for (i=80,j=-1;i>=up;i--){
if (t[P[i].x][P[i].y]<0) continue;
for (j++;j<81&&t[P[j].x][P[j].y]>=0;j++);
swap(P[i], P[j]);
}
for (i=0;it[P[k].x][P[k].y]) k = j;
swap(P[i], P[k]);
label(P[i].x, P[i].y);
}
}
void dfs(int step){
if (step == up) ans = max(ans, bonus);
else {
int x = P[step].x, y = P[step].y;
int q = m - (c[x]|r[y]|s[x/3][y/3]), p;
while (q!=0){
p = q & -q; q -= p;
c[x] |= p; r[y] |= p; s[x/3][y/3] |= p; bonus += l[p]*w[x][y]; dfs(step + 1);
c[x] &=~p; r[y] &=~p; s[x/3][y/3] &=~p; bonus -= l[p]*w[x][y];
}
}
}
int main(){
//freopen("sudoku.in", "r", stdin);
// freopen("sudoku.out", "w", stdout);
init();
int T; cin >> T;
//T = 1;
while (T--){
load(); dfs(0);
cout << ans << endl;
}
}
#include
#include
using namespace std;
const int INF = 1000;
const int m = (1<<9)-1;
int c[9], r[9], s[3][3], l[m]; int a[9][9], w[9][9], t[9][9];
int ans, up, b0, r0;
struct po{
int x, y;
} P[9*9];
void label(int x, int y){
for (int i=0;i<9;i++){
t[i][y]++; t[x][i]++;
}
int i0 = x/3 * 3, j0 = y/3 * 3;
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
t[i0+i][j0+j]++;
}
void init(){
for (int i=0;i<9;i++)
for (int j=0;j<9;j++)
w[i][j] = 10 - max(abs(i-4), abs(j-4));
for (int i=1,p=1;i<=9;i++,p<<=1)
l[p] = i;
}
void load(){
memset(c, 0, sizeof(c)); memset(r, 0, sizeof(r)); memset(s, 0, sizeof(s));
memset(t, 0, sizeof(t)); b0 = 0; r0 = 0; up = 9*9; ans = -1;
int i, j, k;
for (i=0,k=0;i<9;i++)
for (j=0;j<9;j++,k++){
scanf("%d", &a[i][j]); P[k].x = i; P[k].y = j;
if (a[i][j]!=0){
int p = (1<<(a[i][j]-1));
c[i] |= p; r[j] |= p; s[i/3][j/3] |= p;
b0 += a[i][j]*w[i][j]; t[i][j] = -INF;
label(i, j);
up--;
}
else {
r0 += 9 * w[i][j];
}
}
for (i=80,j=-1;i>=up;i--){
if (t[P[i].x][P[i].y]<0) continue;
for (j++;j<81&&t[P[j].x][P[j].y]>=0;j++);
swap(P[i], P[j]);
}
for (i=0;it[P[k].x][P[k].y]) k = j;
swap(P[i], P[k]);
label(P[i].x, P[i].y);
}
for (i=up/7*6;iw[P[k].x][P[k].y]) k = j;
swap(P[i], P[k]);
}
}
void dfs(int step, int bonus, int remain){
if (bonus + remain < ans) return;
if (step == up) ans = bonus;
else {
int x = P[step].x, y = P[step].y;
remain -= 9 * w[x][y];
int q = m - (c[x]|r[y]|s[x/3][y/3]), p;
int n = 0, a[9];
while (q!=0){
p = q & -q; q -= p;
a[n++] = p;
}
while (n--){
p = a[n];
c[x]|=p; r[y]|=p; s[x/3][y/3]|=p;
dfs(step+1, bonus+l[p]*w[x][y], remain);
c[x]&=~p; r[y]&=~p; s[x/3][y/3]&=~p;
}
}
}
int main(){
//freopen("sudoku.in", "r", stdin);
// freopen("sudoku.out", "w", stdout);
init();
int T; cin >> T;
//T = 1;
while (T--){
load(); dfs(0, b0, r0);
cout << ans << endl;
}
}
External link :
http://acm.hit.edu.cn/judge/show.php?Proid=2959&Contestid=0
http://www.rqnoj.cn/Problem_521.html
Background :
NOIP 2009 提高组第四题，（记得当时还是人工录表了来着（大误#），然后好像是搜了40分左右吧， 额，反正去年挂了 。~）
前几次的模拟赛表现的不是很好，反正在回安徽之前我也反思了好长时间，起码那些自己看过的题目再比赛的时候一定要能在限定的时间里编出来呀。
（或者换句话说嘛。。凡是自己放弃的题目一定都是我真的做不出来的。~）
总之接下来的星期里先翻旧题。。。
对于这些当时没有做出来的题，每解决一道都是进步的说。~
