…
\n<\/p>\n
1. \u5bf9\u4e8e\u8fd9\u4e2a\u641c\u7d22\u9898\uff0c\u8003\u5bdf\u641c\u7d22\u7684\u987a\u5e8f\u7684\u8c03\u6574\uff0c\u5728\u4e4b\u524d\u6bd4\u8d5b\u7684\u65f6\u5019\uff0c\u6211\u4e00\u76f4\u5e0c\u671b\u53ef\u4ee5\u63d0\u524d\u641c\u7d22\u5230\u7b54\u6848\uff0c\u4ee5\u5c3d\u53ef\u80fd\u65e9\u7684\u5b8c\u6210\u526a\u679d\uff0c\u4f46\u662f\u5b9e\u9645\u8fd0\u884c\u65f6\u8fd9\u6837\u5199\u4e00\u76f4TLE\uff0c\u66f4\u597d\u7684\u5b89\u6392\u987a\u5e8f\u662f\u5148\u641c\u7d22\u90a3\u4e9b\u9650\u5236\u591a\u7684\u4f4d\u7f6e\u3002<\/p>\n
2. \u5b9e\u9645\u4e2d\uff0c\u8981\u505a\u5230\u5b9e\u65f6\u7684\u7ef4\u62a4\u9650\u5236\u4f4d\u7f6e\uff0c\u4ee3\u4ef7\u592a\u5927\uff0c\u4f46\u662f\u5728\u9884\u5904\u7406\u9636\u6bb5\uff0c\u627e\u5230\u4e00\u7ec4\u8fd1\u4f3c\u7684\u987a\u5e8f\u8fd8\u662f\u53ef\u4ee5\u505a\u5230\u7684\u3002<\/p>\n
3. \u5728\u641c\u7d22\u90e8\u5206\u7684\u4ee3\u7801\u91cc\u7b2c\u56db\u884c\u7684\u90e8\u5206…<\/p>\n
...\r\nvoid dfs(int step){\r\n if (step == up) ans = max(ans, bonus);\r\n else {\r\n int x = P[step].x, y = P[step].y;\r\n int q = m - (c[x]|r[y]|s[x\/3][y\/3]), p;\r\n while (q!=0){\r\n p = q & -q; q -= p;\r\n c[x] |= p; r[y] |= p; s[x\/3][y\/3] |= p; bonus += l[p]*w[x][y]; dfs(step + 1);\r\n c[x] &=~p; r[y] &=~p; s[x\/3][y\/3] &=~p; bonus -= l[p]*w[x][y];\r\n }\r\n }\r\n}\r\n...<\/pre>\n\u6211\u5b9a\u4e49\u4e86\u4e00\u4e2ax, y \u4f5c\u4e3a\u8f85\u52a9\u53d8\u91cf\uff0c\uff08\u5f00\u59cb\u7684\u60f3\u6cd5\u53ea\u662f\u5c11\u6253\u8bb8\u591a\u5b57\u7b26\uff0c\u4ee3\u7801\u683c\u5f0f\u597d\u770b\u8bb8\u591a\uff09\uff0c\u6211\u731c\u60f3\u8fd9\u4e2a\u53ef\u80fd\u4f1a\u589e\u52a0\u5806\u6808\u4f53\u79ef\uff0c\u56e0\u6b64\u5728\u540e\u9762\u5199\u7684\u65f6\u5019\u628a\u5b83\u53bb\u6389\uff0c\uff08\u4f46\u662f\u4ee3\u7801\u53cd\u800c\u901f\u5ea6\u53d8\u6162\u8bb8\u591a\uff080.5s \u5de6\u53f3\uff09\uff0c\u5177\u4f53\u539f\u56e0\u4e0d\u660e\u3002\uff09#<\/p>\n
4. \u4e0b\u9762\u7684\u4ee3\u7801\u662f\u81ea\u6211\u611f\u89c9\u6bd4\u8f83\u7406\u60f3\u7684\u4e00\u4efd\uff0c\u5e0c\u671b\u540c\u65f6\u517c\u987e\u641c\u7d22\u6811\u9650\u5236\u4ee5\u53ca\u6700\u4f18\u526a\u679d\uff0c\u4f46\u662f\u7ecf\u8fc7\u6d4b\u8bd5\u6700\u5feb\u7684\u4ee3\u7801\uff081.36s\uff09\u662f\u628a\u6240\u6709\u6700\u4f18\u526a\u679d\u7684\u90e8\u5206\u5b8c\u5168\u5254\u9664\u6389\u540e\u7684\uff08\u56e0\u6b64\u8fd9\u4efd\u4ee3\u7801\u653e\u5728\u524d\u9762\uff09\u3002\u7b2c\u4e8c\u4e00\u4efd\u5219\u662f\u53ea\u53ef\u4ee5\u505a\u5230 2.00s \u5de6\u53f3\u7684\u6837\u5b50\u3002<\/p>\n
int c[9], r[9], s[3][3];
\n\u8fd9\u4e09\u7ec4\u53d8\u91cf\u662f\u7528\u4f4d\u8fd0\u7b97\u8bb0\u5f55\u9650\u5236\u7684\u4f4d\u7f6e\uff0c
\ncolumn[9] \u8bb0\u5f55\u6a2a\u884c\u7684\u9650\u5236\uff0c row[9] \u8bb0\u5f55\u7eb5\u5217\u7684\u9650\u5236\u3002
\nsub-square[3][3] \u5219\u662f\u8bb0\u5f55\u6bcf\u4e2a\u5b50\u6b63\u65b9\u5f62\uff0c\u56e0\u4e3a\u7275\u6d89\u5230\u6a21\u8fd0\u7b97\uff0c\u8fd9\u4e2a\u90e8\u5206\u6570\u7ec4\u4ece 0 \u5f00\u59cb\u5f00\u4f1a\u66f4\u65b9\u4fbf\u3002<\/p>\n
int a[9][9], w[9][9], l[9];
\na \u6570\u7ec4\u7528\u4e8e\u8bb0\u5f55\u6bcf\u4e2a\u521d\u59cb\u5316\u65f6\u683c\u5b50\u91cc\u586b\u7684\u6570\u5b57\u3002\uff08\u5f53\u7136\u5176\u5b9e\u5728\u540e\u9762\u7684\u4ee3\u7801\u91cc\u4e5f\u7528\u4e0d\u5230\uff0c\u53bb\u6389\u4e5f\u53ef\u3002\uff09
\n…
\nw \u6570\u7ec4\u7528\u4e8e\u8bb0\u5f55\u6bcf\u4e2a\u683c\u5b50\u7684\u6743\u503c\uff0c\u5b83\u548c l \u6570\u7ec4\uff08\u4e00\u4e2a\u5728\u4f4d\u64cd\u4f5c\u7684\u4f1a\u7528\u5230\u7684\u8f85\u52a9\u6570\u7ec4\uff0c\u5177\u4f53\u505a\u4ec0\u4e48\u7684\u81ea\u5df1\u8bfb\u4ee3\u7801\u5566#\uff09\u4e00\u6837\uff0c\u662f\u5728\u6574\u4e2a\u7a0b\u5e8f\u5f00\u59cb\u8bfb\u6570\u636e\u4e4b\u524d\u5148\u9884\u5904\u7406\u597d\u7684\uff0c\u4e4b\u540e\u4e5f\u90fd\u4f5c\u4e3a\u5e38\u91cf\u5b58\u5728\u3002<\/p>\n
\u5176\u5b83\u5219\u6ca1\u6709\u4ec0\u4e48\u8981\u8bf4\u7684\u4e86\uff0c\u54e6\u8fd8\u6709 t \u6570\u7ec4\u7528\u6765\u8bb0\u5f55\u6bcf\u4e2a\u683c\u5b50\u88ab\u9650\u5236\u7684\u6570\u503c\uff0c\u6bcf\u6b21\u53d6\u51fa\u4e00\u4e2a\u88ab\u9650\u5236\u6570\u5b57\u6700\u5927\u7684\u4e00\u4e2a\uff0c\u5bf9\u90a3\u4e9b\u5df2\u7ecf\u6709\u6570\u5b57\u7684\u683c\u5b50\uff0c\u5219\u8d4b\u503c\u4e3a – INF\u3002<\/p>\n
<\/p>\n
\r\n#include \r\n#include \r\n\r\nusing namespace std;\r\nconst int INF = 1000;\r\nconst int m = (1<<9)-1;\r\n\r\nint c[9], r[9], s[3][3], l[m]; \r\nint a[9][9], w[9][9], t[9][9];\r\nint bonus, ans, up;\r\n\r\nstruct po{\r\n int x, y;\r\n} P[9*9];\r\n\r\n\r\nvoid label(int x, int y){\r\n for (int i=0;i<9;i++){\r\n t[i][y]++; t[x][i]++;\r\n }\r\n\r\n int i0 = x\/3 * 3, j0 = y\/3 * 3;\r\n for (int i=0;i<3;i++)\r\n for (int j=0;j<3;j++)\r\n t[i0+i][j0+j]++;\r\n}\r\n\r\n\r\nvoid init(){\r\n for (int i=0;i<9;i++)\r\n for (int j=0;j<9;j++)\r\n w[i][j] = 10 - max(abs(i-4), abs(j-4));\r\n\r\n for (int i=1,p=1;i<=9;i++,p<<=1)\r\n l[p] = i;\r\n}\r\n\r\nvoid load(){\r\n memset(c, 0, sizeof(c)); memset(r, 0, sizeof(r)); memset(s, 0, sizeof(s));\r\n memset(t, 0, sizeof(t)); bonus = 0; up = 9*9; ans = -1;\r\n\r\n int i, j, k;\r\n for (i=0,k=0;i<9;i++)\r\n for (j=0;j<9;j++,k++){\r\n scanf(\"%d\", &a[i][j]); P[k].x = i; P[k].y = j;\r\n if (a[i][j]!=0){\r\n int p = (1<<(a[i][j]-1));\r\n c[i] |= p; r[j] |= p; s[i\/3][j\/3] |= p;\r\n bonus += a[i][j]*w[i][j]; t[i][j] = -INF;\r\n label(i, j);\r\n up--;\r\n }\r\n }\r\n\r\n for (i=80,j=-1;i>=up;i--){\r\n if (t[P[i].x][P[i].y]<0) continue;\r\n for (j++;j<81&&t[P[j].x][P[j].y]>=0;j++);\r\n swap(P[i], P[j]);\r\n }\r\n\r\n for (i=0;it[P[k].x][P[k].y]) k = j;\r\n swap(P[i], P[k]);\r\n label(P[i].x, P[i].y);\r\n }\r\n}\r\n\r\nvoid dfs(int step){\r\n if (step == up) ans = max(ans, bonus);\r\n else {\r\n int x = P[step].x, y = P[step].y;\r\n int q = m - (c[x]|r[y]|s[x\/3][y\/3]), p;\r\n while (q!=0){\r\n p = q & -q; q -= p;\r\n c[x] |= p; r[y] |= p; s[x\/3][y\/3] |= p; bonus += l[p]*w[x][y]; dfs(step + 1);\r\n c[x] &=~p; r[y] &=~p; s[x\/3][y\/3] &=~p; bonus -= l[p]*w[x][y];\r\n }\r\n }\r\n}\r\n\r\n\r\nint main(){\r\n\r\n \/\/freopen(\"sudoku.in\", \"r\", stdin);\r\n \/\/ freopen(\"sudoku.out\", \"w\", stdout);\r\n\r\n init();\r\n int T; cin >> T;\r\n \/\/T = 1;\r\n while (T--){\r\n load(); dfs(0);\r\n cout << ans << endl;\r\n }\r\n}\r\n<\/pre>\n\r\n#include \r\n#include \r\n\r\nusing namespace std;\r\nconst int INF = 1000;\r\nconst int m = (1<<9)-1;\r\n\r\nint c[9], r[9], s[3][3], l[m]; int a[9][9], w[9][9], t[9][9]; \r\n\r\n\r\nint ans, up, b0, r0;\r\n\r\nstruct po{\r\n int x, y;\r\n} P[9*9];\r\n\r\n\r\nvoid label(int x, int y){\r\n for (int i=0;i<9;i++){\r\n t[i][y]++; t[x][i]++;\r\n }\r\n\r\n int i0 = x\/3 * 3, j0 = y\/3 * 3;\r\n for (int i=0;i<3;i++)\r\n for (int j=0;j<3;j++)\r\n t[i0+i][j0+j]++;\r\n}\r\n\r\n\r\nvoid init(){\r\n for (int i=0;i<9;i++)\r\n for (int j=0;j<9;j++)\r\n w[i][j] = 10 - max(abs(i-4), abs(j-4));\r\n\r\n for (int i=1,p=1;i<=9;i++,p<<=1)\r\n l[p] = i;\r\n}\r\n\r\nvoid load(){\r\n memset(c, 0, sizeof(c)); memset(r, 0, sizeof(r)); memset(s, 0, sizeof(s));\r\n memset(t, 0, sizeof(t)); b0 = 0; r0 = 0; up = 9*9; ans = -1;\r\n\r\n\r\n int i, j, k;\r\n for (i=0,k=0;i<9;i++)\r\n for (j=0;j<9;j++,k++){\r\n scanf(\"%d\", &a[i][j]); P[k].x = i; P[k].y = j;\r\n\r\n if (a[i][j]!=0){\r\n int p = (1<<(a[i][j]-1));\r\n c[i] |= p; r[j] |= p; s[i\/3][j\/3] |= p;\r\n b0 += a[i][j]*w[i][j]; t[i][j] = -INF;\r\n label(i, j);\r\n up--;\r\n }\r\n else {\r\n r0 += 9 * w[i][j];\r\n }\r\n }\r\n\r\n for (i=80,j=-1;i>=up;i--){\r\n if (t[P[i].x][P[i].y]<0) continue;\r\n for (j++;j<81&&t[P[j].x][P[j].y]>=0;j++);\r\n swap(P[i], P[j]);\r\n }\r\n\r\n for (i=0;it[P[k].x][P[k].y]) k = j;\r\n swap(P[i], P[k]);\r\n label(P[i].x, P[i].y);\r\n }\r\n\r\n for (i=up\/7*6;iw[P[k].x][P[k].y]) k = j;\r\n swap(P[i], P[k]);\r\n }\r\n}\r\n\r\nvoid dfs(int step, int bonus, int remain){\r\n if (bonus + remain < ans) return;\r\n if (step == up) ans = bonus;\r\n else {\r\n int x = P[step].x, y = P[step].y;\r\n remain -= 9 * w[x][y];\r\n int q = m - (c[x]|r[y]|s[x\/3][y\/3]), p;\r\n\r\n int n = 0, a[9];\r\n while (q!=0){\r\n p = q & -q; q -= p;\r\n a[n++] = p;\r\n }\r\n\r\n while (n--){\r\n p = a[n];\r\n c[x]|=p; r[y]|=p; s[x\/3][y\/3]|=p;\r\n dfs(step+1, bonus+l[p]*w[x][y], remain);\r\n c[x]&=~p; r[y]&=~p; s[x\/3][y\/3]&=~p;\r\n }\r\n }\r\n}\r\n\r\n\r\nint main(){\r\n\r\n \/\/freopen(\"sudoku.in\", \"r\", stdin);\r\n \/\/ freopen(\"sudoku.out\", \"w\", stdout);\r\n\r\n init();\r\n int T; cin >> T;\r\n \/\/T = 1;\r\n while (T--){\r\n load(); dfs(0, b0, r0);\r\n cout << ans << endl;\r\n }\r\n}\r\n<\/pre>\n<\/bk><\/bk><\/p>\n
External link :<\/h3>\n
http:\/\/acm.hit.edu.cn\/judge\/show.php?Proid=2959&Contestid=0
\nhttp:\/\/www.rqnoj.cn\/Problem_521.html
\n<\/bk><\/p>\n
Background :<\/h3>\n
NOIP 2009 \u63d0\u9ad8\u7ec4\u7b2c\u56db\u9898\uff0c\uff08\u8bb0\u5f97\u5f53\u65f6\u8fd8\u662f\u4eba\u5de5\u5f55\u8868\u4e86\u6765\u7740\uff08\u5927\u8bef#\uff09\uff0c\u7136\u540e\u597d\u50cf\u662f\u641c\u4e8640\u5206\u5de6\u53f3\u5427\uff0c \u989d\uff0c\u53cd\u6b63\u53bb\u5e74\u6302\u4e86 \u3002~\uff09<\/p>\n
\u524d\u51e0\u6b21\u7684\u6a21\u62df\u8d5b\u8868\u73b0\u7684\u4e0d\u662f\u5f88\u597d\uff0c\u53cd\u6b63\u5728\u56de\u5b89\u5fbd\u4e4b\u524d\u6211\u4e5f\u53cd\u601d\u4e86\u597d\u957f\u65f6\u95f4\uff0c\u8d77\u7801\u90a3\u4e9b\u81ea\u5df1\u770b\u8fc7\u7684\u9898\u76ee\u518d\u6bd4\u8d5b\u7684\u65f6\u5019\u4e00\u5b9a\u8981\u80fd\u5728\u9650\u5b9a\u7684\u65f6\u95f4\u91cc\u7f16\u51fa\u6765\u5440\u3002
\n\uff08\u6216\u8005\u6362\u53e5\u8bdd\u8bf4\u561b\u3002\u3002\u51e1\u662f\u81ea\u5df1\u653e\u5f03\u7684\u9898\u76ee\u4e00\u5b9a\u90fd\u662f\u6211\u771f\u7684\u505a\u4e0d\u51fa\u6765\u7684\u3002~\uff09<\/p>\n
\u603b\u4e4b\u63a5\u4e0b\u6765\u7684\u661f\u671f\u91cc\u5148\u7ffb\u65e7\u9898\u3002\u3002\u3002
\n\u5bf9\u4e8e\u8fd9\u4e9b\u5f53\u65f6\u6ca1\u6709\u505a\u51fa\u6765\u7684\u9898\uff0c\u6bcf\u89e3\u51b3\u4e00\u9053\u90fd\u662f\u8fdb\u6b65\u7684\u8bf4\u3002~<\/p>\n","protected":false},"excerpt":{"rendered":"
…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-128","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-24","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/128","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=128"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/128\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=128"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=128"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=128"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}