\u7ed9\u5b9a\u4e24\u4e2a\u5b57\u7b26\u4e32\uff0c\u8981\u6c42\u4e00\u4e2a\u5206\u7ec4\u65b9\u6848\u4f7f\u5f97\u4e0d\u76f8\u4f3c\u5ea6\u5c3d\u53ef\u80fd\u5c11\uff0c\u4e0d\u76f8\u4f3c\u5ea6\u5b9a\u4e49\u4e3a\u5206\u7684\u6bb5\u6570*m\uff0c\u7136\u540e\u6bcf\u4e00\u6bb5\u4e0d\u76f8\u4f3c\u5ea6\u6c42\u548c\u540e\u518d\u5e73\u65b9…
\n…
\n<\/p>\n
\u7ecf\u5e38\u4f1a\u9047\u5230\u8fd9\u6837\u7684\u5206\u7ec4\u7c7bDP\u9898\uff0c\u5176\u6bcf\u4e00\u7ec4\u7684\u503c\u5148\u6c42\u548c\u540e\u518d\u8fdb\u884c\u8ba1\u7b97\uff0c\u4e14\u6240\u6709\u7684\u503c\u540c\u53f7\uff08\u90fd\u662f\u6b63\u6570\u6216\u90fd\u662f\u8d1f\u6570\uff09\uff0cN\u7684\u8303\u56f4\u5f88\u5927\uff0c\u7528O\uff08N^2\uff09\u7684DP\u4f1aTLE\uff0c\u6b64\u65f6\uff0c\u4e00\u79cd\u5f88\u91cd\u8981\u7684\u4f18\u5316\u662f\uff1a\u659c\u7387\u4f18\u5316\u3002<\/p>\n
\r\n\/*\r\n\tAuthor : xiaodao\r\n\tProb : RQnoj 418. \u6d6a\u6d6a\u7684\u5c0f\u7231\u597d\r\n\tStatus : TLE (60)\r\n\tLast modify : ...\r\n*\/\r\n#include <iostream>\r\nusing namespace std;\r\nconst long long INF = (long long)(1) << 60;\r\nconst int N = 200001;\r\nlong long dp[N], s[N];\r\nint n, m;\r\n\r\nvoid init(){\r\n cin >> n >> m;\r\n string a, b; cin >> a >> b;\r\n\tfor (int i=1;i<=n;i++){\r\n s[i] = s[i-1] + abs(int(a[i-1]-b[i-1]));\r\n }\r\n}\r\n\r\nvoid solve(){\r\n for (int i=1;i<=n;i++){\r\n\t\tdp[i] = INF;\r\n\t\tfor (int j=0;j<i;j++)\r\n\t\t\tdp[i] = min(dp[i], dp[j] + (s[i]-s[j])*(s[i]-s[j]) + m);\r\n }\r\n}\r\n\r\nint main(){\r\n init(); solve();\r\n cout << dp[n]-m << endl;\r\n}\r\n<\/pre>\n\r\n\/*\r\n Author : xiaodao\r\n Prob : RQnoj 418. \u6d6a\u6d6a\u7684\u5c0f\u7231\u597d\r\n Status : Accepted\r\n Last modify : ..\r\n *\/\r\n#include <iostream>\r\n\r\nusing namespace std;\r\nconst double INF = 1e10;\r\nconst int N = 200001;\r\nlong long dp[N], s[N];\r\nint n, m;\r\n\r\ndouble h(int j1, int j2){\r\n\tif (s[j2] - s[j1] == 0) return INF;\r\n\treturn (dp[j2] - dp[j1])\/(s[j2] - s[j1]) + s[j1] + s[j2];\r\n}\r\n\r\n\r\nvoid init(){\r\n cin >> n >> m;\r\n string a, b; cin >> a >> b;\r\n\tfor (int i=1;i<=n;i++){\r\n s[i] = s[i-1] + abs(int(a[i-1]-b[i-1]));\r\n }\r\n}\r\n\r\nvoid solve(){\r\n\tint Q[N] = {0}, L = 0, R = 0;\r\n \r\n\tfor (int i=1;i<=n;i++){\r\n\t\twhile ( L < R && h(Q[L], Q[L+1]) < 2 * s[i]) L++;\r\n\t\tdp[i] = dp[Q[L]] + (s[i]-s[Q[L]]) * (s[i]-s[Q[L]]) + m;\r\n\t\twhile ( L < R && h(Q[R-1], Q[R]) >= h(Q[R] ,i) ) R--;\r\n\t\tQ[++R] = i;\r\n }\r\n}\r\n\r\nint main(){\r\n init(); solve();\r\n cout << dp[n] - m << endl;\r\n}\r\n<\/pre>\n\r\n\/*\r\n\tAuthor : xiaodao\r\n\tProb : RQnoj 418. \u6d6a\u6d6a\u7684\u5c0f\u7231\u597d\r\n\tStatus : Accepted\r\n\tLast modify : ...\r\n*\/\r\n#include <iostream>\r\nusing namespace std;\r\nconst int INF = 1000000000;\r\nconst int N = 200001;\r\nlong long dp[N], s[N];\r\nint n, m;\r\n\r\nint H(int i, int j){\r\n\treturn dp[i] - dp[j] + s[i]*s[i] - s[j]*s[j];\r\n}\r\n\r\n\r\nvoid init(){\r\n cin >> n >> m;\r\n string a, b; cin >> a >> b;\r\n\tfor (int i=1;i<=n;i++){\r\n s[i] = s[i-1] + abs(int(a[i-1]-b[i-1]));\r\n }\r\n}\r\n\r\nvoid solve(){\r\n\tint Q[N] = {0}, L = 0, R = 0;\r\n\t\r\n for (int i=1;i<=n;i++){\r\n\t\twhile ( L < R && H(Q[L], Q[L+1])>=s[i]*2*(s[Q[L]]-s[Q[L+1]]) ) L++;\r\n\t\tdp[i] = dp[Q[L]] + (s[i]-s[Q[L]])*(s[i]-s[Q[L]]) + m;\r\n\t\twhile ( L < R && H(Q[R-1], Q[R])*(s[Q[R]]-s[i])>=H(Q[R], i)*(s[Q[R-1]]-s[Q[R]]) ) R--;\r\n\t\tQ[++R] = i;\r\n }\r\n}\r\n\r\nint main(){\r\n init(); solve();\r\n cout << dp[n]-m << endl;\r\n}\r\n<\/pre>\n<\/bk>
\ndp[i] \u8868\u793a\u8003\u5bdf\u524di\u4e2a\u5b57\u7b26\uff0c\u5206\u6bb5\u540e\u5f62\u6210\u7684\u6700\u5c0f\u4ee3\u4ef7\u3002
\n\\[dp[i] = min\\{dp[j] + (s[i]-s[j])^2\\} + m \\ |\\ 0\\leq j<\/bk>
\n\u4e0b\u9762\u7684\u6b65\u9aa4\u65f6\u8003\u5bdf\u679a\u4e3e\u65f6\u7684\u524d\u540e\u4e24\u7ec4\u53d8\u91cf j1, j2\uff0cj1 < j2 \u4e14\u51b3\u7b56 j1 \u6bd4 j2 \u66f4\u4f18\uff0c\u636e\u6b64\u5217\u51fa\u4e0d\u7b49\u5f0f\uff0c\u5e76\u5bf9\u5176\u8fdb\u884c\u79fb\u9879\u3001\u53d8\u53f7\uff08\u6ce8\u610f\u5230 s \u6570\u7ec4\u4e00\u5b9a\u5355\u8c03\u9012\u589e\u7684\u7279\u6027\uff0cs[j1] - s[j2] < 0 \uff09\u7b49\u64cd\u4f5c\uff0c\u76f4\u5230\u4e0d\u7b49\u5f0f\u4e2d\u6240\u6709\u7684\u5df2\u77e5\u91cf\u90fd\u88ab\u79fb\u5230\u4e0d\u7b49\u53f7\u540c\u4e00\u8fb9\uff08\u4e00\u822c\u662f\u53f3\u8fb9\uff09\u4e3a\u6b62\u3002\n\n\\[dp[j_1] + (s[i]-s[j_1])^2 + m< dp[j_2] + (s[i]-s[j_2])^2 + m\\]\n\\[dp[j_1] - dp[j_2] + s[j_1]^2 - s[j_2]^2 < 2s[i]s[j_1] - 2s[i]s[j_2]\\]\n\u4f7f\u7528\u5e73\u65b9\u5dee\u516c\u5f0f\n\n\\[dp[j_1] - dp[j_2] + (s[j_1] + s[j_2])(s[j_1] - s[j_2]) < 2s[i](s[j_1] - s[j_2])\\]\n\u9664\u8fc7\u6765 ...\t\n\n\\[\\frac{dp[j_2] - dp[j_1]}{s[j_2] - s[j_1]} + s[j_2] + s[j_1] > 2s[i]\\]<\/p>\n<\/bk><\/bk>
\n\u6211\u4eec\u53d1\u73b0\u5de6\u8fb9\u7684\u5f0f\u5b50\u5df2\u7ecf\u540c i \u65e0\u5173\uff0c\u5236\u4f5c\u8f85\u52a9\u51fd\u6570, <\/p>\n
\\[h(j_1, j_2) = \\frac{dp[j_2] – dp[j_1]}{s[j_2] – s[j_1]} + s[j_2] + s[j_1]\\]<\/p>\n
<\/bk><\/bk>
\n\u4e8e\u662f\u5f53\u51b3\u7b56 j1 \u4f18\u4e8e\u51b3\u7b56\u5f53\u4e14\u4ec5\u5f53 $$h(j_1, j_2) > 2s[i]$$ …<\/p>\n
<\/bk><\/bk>
\n\u4e3a\u4e86\u8981\u53ef\u4ee5\u5e94\u7528\u5355\u8c03\u961f\u5217\uff0c\u63a5\u4e0b\u6765\u8981\u6316\u6398 h \u51fd\u6570\u7684\u4e00\u4e2a\u91cd\u8981\u6027\u8d28\uff0c\u8003\u5bdf\u524d\u540e\u4e00\u7ec4\u51b3\u7b56\u53d8\u91cf\uff0cj1 < j2 < j3\uff0c\u4e14\u6ee1\u8db3 $$h(j_1, j_2) \\geq h(j_2, j_3)$$\n\u90a3\u4e48\u5206\u7c7b\u8ba8\u8bba\u4ee5\u540e\u53ef\u4ee5\u80af\u5b9a\uff0c j2\u4e00\u5b9a\u4e0d\u4f1a\u662f\u6700\u4f18\u7684\u51b3\u7b56\u3002\n1: h(j1, j2) > s[i] … \u7acb\u5373\u53ef\u5f97 j1 \u4f18\u4e8e j2\u3002
\n2: h(j1, j2) <= s[i] \uff0c\u90a3\u4e48\u6b64\u65f6\uff0c \u56e0\u4e3a h(j2, j3) \u6bd4 h(j1, j2) \u8fd8\u8981\u5c0f\uff0c\u56e0\u6b64 j2 \u6bd4 j3 \u52a3\u3002\n\uff08 h(j2, j3) <= h(j1, j2) <= s[i] \uff09\n\n\u56e0\u6b64\uff0c\u7528\u5355\u8c03\u961f\u5217\u4fdd\u5b58\u4e00\u7ec4\u76f8\u90bb\u72b6\u6001\u95f4 h \u51fd\u6570\u9012\u51cf\u7684\u51b3\u7b56\u3002\uff08\u554a\uff0c\u662f\u9012\u589e\u6655\u4e86\u6211\u5df2\u7ecf\u3002\uff5e\uff09\n... \u4e14\u6700\u4f18\u65b9\u6848\u4e00\u5b9a\u5728\u6700\u5de6\u8fb9\u3002\uff03\uff08\u521a\u597d\u548c\u524d\u9762\u7684\u4e00\u4e2a\u6027\u8d28\u7ec4\u5408\u8d77\u6765\u7528... \uff09\n\n\n\n
External link :<\/h3>\n
http:\/\/www.rqnoj.cn\/Problem_418.html
\nhttp:\/\/hi.baidu.com\/matobeatjollwish\/blog\/item\/b30fea355aa3c4365bb5f509.html ( \u5931\u6548
\nhttp:\/\/www.csie.ntnu.edu.tw\/~u91029\/WordWrap.html<\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description : \u7ed9\u5b9a\u4e24\u4e2a\u5b57\u7b26\u4e32\uff0c\u8981\u6c42\u4e00\u4e2a\u5206\u7ec4\u65b9\u6848\u4f7f\u5f97\u4e0d\u76f8\u4f3c\u5ea6\u5c3d\u53ef\u80fd\u5c11\uff0c\u4e0d\u76f8\u4f3c\u5ea6\u5b9a\u4e49\u4e3a\u5206\u7684\u6bb5\u6570*m\uff0c\u7136\u540e\u6bcf\u4e00\u6bb5\u4e0d\u76f8\u4f3c\u5ea6\u6c42\u548c\u540e\u518d\u5e73\u65b9… …<\/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-142","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-2i","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/142","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=142"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/142\/revisions"}],"predecessor-version":[{"id":565,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/142\/revisions\/565"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}