\u6309\u7167 250 -> 1000 -> 550… \u7684\u987a\u5e8f\u5f00\u7684\u9898\u3002\u3002
\n\u7ed3\u679c 1000 \u6ca1\u64b8\u51fa\u6765 250 \u53c8\u6302\u4e86\u679c\u65ad\u7206\u4e86 0 \u3002\u3002\uff08\u4f46\u662f\u5c45\u7136 Unrate \u4e86\u6211\u4f1a\u4e71\u8bf4 .. ??\u3002\u3002\uff09
\n\u3002\u3002\u3002\u8a00\u5f52\u6b63\u4f20\u3002\u3002<\/p>\n
<\/p>\n<\/h3>\n
Brief description: <\/h3>\n
550:
\n…
\n1000\uff1a
\n\u7ed9\u5b9a\u4e00\u9897\u6811\u72b6\u8ff7\u5bab\uff0c\u5b9a\u4e49\u4e00\u6b21\u67d3\u8272\u64cd\u4f5c\u4e3a\uff1a\u6bcf\u6b21\u8986\u76d6\u4e00\u683c\u70b9\uff0c\u540c\u65f6\u8986\u76d6\u5176\u4e0a\u4e0b\u5de6\u53f3\u56db\u4e2a\u65b9\u5411\u6240\u6709\u53ef\u4ee5\u5ef6\u4f38\u5230\u7684\u5176\u5b83\u683c\u70b9\u3002
\n\u95ee\u81f3\u5c11\u8fdb\u884c\u591a\u5c11\u6b21\u64cd\u4f5c\u53ef\u5b8c\u6210\u67d3\u8272\u3002
\n\uff08.. . N \u2264 50 .. \uff09 <\/p>\n<\/h3>\n
Analysis: <\/h3>\n
… \u73b0\u573a\u751f\u7b97\u6cd5\uff1a\u5bf9\u6bcf\u4e2a\u8f6c\u89d2\u4f4d\u7f6e\u5efa\u70b9\uff0c\u82e5\u4e24\u4e2a\u8f6c\u89d2\u4f4d\u7f6e\u901a\u8fc7\u8def\u5f84\u76f8\u8fde\u5219\u8fde\u8fb9\u3002\u3002\u3002
\n\u3002\u3002\u4e8e\u662f\u8f6c\u5316\u6210\u4e00\u4e2a\u53d8\u5f62\u7684\u652f\u914d\u96c6\u95ee\u9898\u3002\u3002\uff08\u70b9\u96c6\u652f\u914d\u8fb9\u96c6\u3002\u3002\uff09\u3002\u3002<\/p>\n
\uff08\u4e8e\u662f\u8fd9\u4e2a\u65b9\u6cd5\u8fd8\u6709\u5f85\u7814\u7a76\u3002\u3002\u3002\uff09<\/p>\n
\u7b2c\u4e8c\u79cd\u65b9\u6cd5\u662f\u5bf9\u6bcf\u6761\u6a2a\u7ad6\u8fb9\u5206\u79bb\uff0c\u6839\u636e\u8f6c\u89d2\u4f4d\u7f6e\u8fde\u8fb9\u3002\u3002\u8f6c\u6362\u6210\u4e8c\u5206\u56fe\u8fb9\u8986\u76d6\u95ee\u9898\u3002\u3002
\n\u3002\u3002\u4f46\u662f\u6709\u4e00\u4e9b\u5947\u602a\u7684\u6811\u72b6\u6570\u636e\u8fd9\u79cd\u65b9\u6cd5\u4f1a\u9519\u3002\u3002\u3002<\/p>\n
\u3002\u3002\u3002\u770b\u6765\u8fd9\u79cd\u5efa\u6a21\u65b9\u6cd5\u597d\u50cf\u4f1a\u4e22\u62d3\u6251\u4fe1\u606f\u3002\u3002\uff08\u3002\u3002\u6211\u8bd5\u56fe\u8d2a\u5fc3\u4fee\u6b63\u3002\u3002\u4f46\u770b\u8d77\u6765\u8fd9\u79cd\u65b9\u6cd5\u5df2\u7ecf\u6ca1\u6551\u4e86\u3002\u3002\uff09
\n\u3002\u3002\u4e8e\u662f\u5bf9\u6bcf\u4e2a\u5b64\u7acb\u7684\u683c\u70b9\u5206\u522b\u5efa\u70b9\u3002\u3002\u8fdb\u884c\u88f8\u7684\u52a8\u6001\u89c4\u5212\u3002\u3002<\/p>\n
\u7136\u540e\u7c7b\u6bd4\u6811\u7684\u652f\u914d\u96c6\u95ee\u9898\uff0c\u5c06\u72b6\u6001\u5206\u4ee5\u4e0b\u4e09\u7c7b\u3002\u3002\u3002<\/p>\n
\r\nconst int None = 0, Cover = 1, Extend = 2; \r\n\/\/ \u8fd8\u672a\u88ab\u8986\u76d6... \u88ab\u8986\u76d6\u4f46\u4e0d\u53ef\u5ef6\u4f38 ... \u88ab\u8986\u76d6\u4e14\u53ef\u5ef6\u4f38...\r\n<\/pre>\n\u4e4b\u540e\u679a\u4e3e\u63d2\u5934\u5f62\u72b6\u5206\u60c5\u51b5\u8ba8\u8bba\u72b6\u6001\u8f6c\u79fb \u6216 \u505a\u6811\u4e0a\u80cc\u5305\u5373\u53ef\u3002\u3002\u72b6\u6001\u8f6c\u79fb\u8bf7\u770b\u4e0b\u56fe\u3002\u3002\u95ee\u53f7\u5730\u533a\u8bf7\u81ea\u884c\u8111\u8865\u3002\u3002<\/p>\n
\r\n-\/0\/1\r\n? 0 ? \/\/ None\r\n\r\n -\/1\r\n? 1 ? \/\/ Cover\r\n\r\n 2\r\n? 2 ? \/\/ Extend\r\n\r\n x\r\nx 2 x \/\/ Guard\r\n<\/pre>\n\u989d\u3002\u3002\u4e0b\u9762\u4ee5\u7b2c\u4e09\u526f\u56fe\u4e3e\u4f8b\uff0c\u8981\u6c42\u6b63\u524d\u65b9\u533a\u57df\u5fc5\u987b\u662f Extend\uff0c
\n\u540c\u65f6\u5de6\u53f3\u4e24\u8fb9\u8981\u80fd\u5b89\u5168\u8986\u76d6\uff0c\u8981\u4e0d\u7136\u662f\u6709\u4e00\u4e2a Extend\uff0c\u8981\u4e0d\u7136\u662f\u4e24\u9762\u90fd\u662f Cover \u3002\u3002\u3002
\n\u5177\u4f53\u4e66\u5199\u7684\u65f6\u5019\u7528 Delta \u5b58\u4e00\u4e2a\u5dee\u503c\u3002\u3002\u548c\u6811\u7684\u652f\u914d\u96c6\u7684\u65b9\u6cd5\u4e00\u6837\u3002\u3002<\/p>\n\u53e6\u5916\u503c\u5f97\u6ce8\u610f\u7684\u662f\uff0c\u5bf9\u4e8e\u6839\u7ed3\u70b9\u9700\u8981\u9ed8\u8ba4\u4e00\u4e2a\u6b63\u65b9\u5411\u3002<\/p>\n
\r\nconst int dx[] = {1, -1, 0, 0};\r\nconst int dy[] = {0, 0, 1, -1};\r\nconst int N = 50, NN = N * N;\r\n\r\nbool Grid[N][N]; int dp[3][N][N];\r\nint n, m;\r\n\r\ninline int _R(int d){\r\n return d ^ 1;\r\n}\r\n\r\ninline int inGrid(int x, int y){\r\n return x >= 0 && x < n && y >= 0 && y < m;\r\n}\r\n\r\ninline bool legal(int x, int y){\r\n return inGrid(x, y) && Grid[x][y];\r\n}\r\n\r\n#define u0 dp[0][x][y]\r\n#define u1 dp[1][x][y]\r\n#define u2 dp[2][x][y]\r\n#define v0 dp[0][xx][yy]\r\n#define v1 dp[1][xx][yy]\r\n#define v2 dp[2][xx][yy]\r\n#define v12 min(v1, v2)\r\n#define v012 min(v0, v12)\r\n\r\nvoid dfs(int x, int y, int dir){\r\n\r\n int c_ = 0, c0 = INF, c1 = INF, c2 = INF;\r\n int s1 = 0, s12 = 0, s012 = 0, delta = INF, guard = 1;\r\n\r\n bool leaf = true; REP(i, 4){\r\n if (_R(i) == dir) continue;\r\n int xx = x + dx[i], yy = y + dy[i];\r\n if (legal(xx, yy)){\r\n dfs(xx, yy, i); if (i == dir || dir == -1 && i <= 1) c_ = INF, c0 = v0, c1 = v1, c2 = v2;\r\n else s1 += v1, s12 += v12, s012 += v012, checkMin(delta, v2 - v012);\r\n guard += v012, leaf = false;\r\n }\r\n }\r\n\r\n if (leaf) u0 = 0, u1 = INF, u2 = 1;\r\n else {\r\n s012 += delta, u0 = min(c_, c0, c1) + min(s1, s012), u1 = min(c_, c1) + s012;\r\n u2 = min(c2 + min(s1, s012), guard);\r\n }\r\n}\r\n\r\nclass FoxBomb {\r\npublic:\r\n\tint getMinimumCost(vector <string> grid){\r\n\r\n n = SZ(grid), m = SZ(grid[0]); int x0 = -1, y0;\r\n\t REP_2(i, j, n, m) Grid[i][j] = grid[i][j] == '.';\r\n\r\n REP_2(x, y, n, m) if (Grid[x][y]) REP(d, 4){\r\n int xx = x + dx[d], yy = y + dy[d];\r\n if (legal(xx, yy)) x0 = xx, y0 = yy;\r\n }\r\n\r\n dfs(x0, y0, -1);\r\n return min(dp[1][x0][y0], dp[2][x0][y0]);\r\n\t}\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u6309\u7167 250 -> 1000 -> 550… \u7684\u987a\u5e8f\u5f00\u7684\u9898\u3002\u3002 \u7ed3\u679c 1000 \u6ca1\u64b8\u51fa\u6765 250 \u53c8\u6302\u4e86\u679c\u65ad\u7206\u4e86 0 \u3002\u3002\uff08\u4f46\u662f\u5c45\u7136 Unrate \u4e86\u6211\u4f1a\u4e71\u8bf4 .. ??\u3002\u3002\uff09 \u3002\u3002\u3002\u8a00\u5f52\u6b63\u4f20\u3002\u3002<\/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":[17],"tags":[63],"class_list":["post-173","post","type-post","status-publish","format-standard","hentry","category-topcoder","tag-63"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-2N","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/173","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=173"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/173\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=173"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=173"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}