{"id":603,"date":"2020-11-01T12:23:58","date_gmt":"2020-11-01T04:23:58","guid":{"rendered":"https:\/\/blog.sukasuka.cn\/?p=603"},"modified":"2021-08-21T18:13:13","modified_gmt":"2021-08-21T10:13:13","slug":"p5017-%e6%91%86%e6%b8%a1%e8%bd%a6","status":"publish","type":"post","link":"https:\/\/blog.sukasuka.cn\/?p=603","title":{"rendered":"P5017 \u6446\u6e21\u8f66"},"content":{"rendered":"<p>\u5c06\u65f6\u95f4\u62bd\u8c61\u4e3a\u4e00\u6839\u6570\u8f74\uff0c\u5c06\u5176\u5206\u4e3ak\u6bb5\uff0c\u6bcf\u4e00\u6bb5\u4e2d\u7684\u53f3\u7aef\u70b9\u8868\u793a\u5f53\u524d\u7aef\u70b9\u53d1\u4e86\u4e00\u73ed\u8f66\uff0c\u6b64\u65f6t&lt;=i\u7684\u65c5\u5ba2\u5747\u53ef\u4e0a\u8f66\u3002<\/p>\n<p>\u800c\u5bf9\u4e8e\u4e00\u4e2a\u4f4d\u4e8ej(j&lt;=i)\u4f4d\u7f6e\u7684\u65c5\u5ba2\uff0c\u5176\u7b49\u8f66\u65f6\u95f4\u4e3a(i-j)\u3002\u6211\u4eec\u9700\u8981\u6c42\u51fa\u4f4d\u4e8e\u533a\u95f4(??,i]\u5185\u65c5\u5ba2\u7b49\u8f66\u65f6\u95f4\u603b\u548c\u3002\u53ef\u4ee5\u7528\u524d\u7f00\u548c\u4f18\u5316\u8fd9\u4e2a\u6b65\u9aa4\u3002<\/p>\n<p>\u5177\u4f53\u64cd\u4f5c\u4e3a\u4f7f\u7528\u4e24\u4e2a\u524d\u7f00\u548c\uff0c\u7b2c\u4e00\u4e2acnt\u8bb0\u5f55(i,j]\u4e2d\u7684\u65c5\u5ba2\u4e2a\u6570\uff0c\u7b2c\u4e8c\u4e2asum\u8bb0\u5f55(i,j]\u7684\u65f6\u95f4\u5dee\uff0c\u5219dis=(cnt[j]-cnt[i])*i-(sum[j]-sum[i])<\/p>\n<p>dp[i]\u8868\u793a(-\u221e,i]\u4ee5i\u4e3a\u6700\u540e\u4e00\u6bb5\u7684\u7ed3\u5c3e\u65f6\u4ea7\u751f\u7684\u603b\u4ee3\u4ef7\u3002<\/p>\n<p>\u663e\u7136\uff0c\u5bf9\u4e8e\u4e00\u4e2a\u4f4d\u7f6ei\uff0c\u5176\u53ef\u80fd\u6765\u81ea\u7684\u4f4d\u7f6e\u4e3a[i-2m,i-m]\uff08&lt;=i-2m\u7684\u5176\u4ed6\u4f4d\u7f6eans\u4e0d\u4f1a\u66f4\u4f18\uff09\uff0c\u56e0\u6b64\uff0c\u4e0a\u6587(??,i]\u7684\u679a\u4e3e\u8303\u56f4\u4fbf\u4e3a[i-2m,i-m]<\/p>\n<p>\u8fd8\u6709\u4e00\u4e2a\u6bd4\u8f83\u663e\u7136\u7684\u4f18\u5316\uff1a\u5f53\u5f53\u524d\u679a\u4e3e\u7684\u533a\u57df[j,i]\u5185\u6ca1\u6709\u65c5\u5ba2\u65f6\uff0c\u6211\u4eec\u53ef\u4ee5\u76f4\u63a5\u7ee7\u627fdp[i-m]\u7684\u7b54\u6848\u5e76\u8df3\u8fc7\u8fd9\u4e2a\u65f6\u95f4\u70b9\u3002<\/p>\n<div class=\"hcb_wrap\">\n<pre class=\"prism line-numbers lang-cpp\" data-lang=\"C++\"><code>\/* <code data-v-728f1152=\"\" data-v-796309f8=\"\" class=\"language-cpp\" data-rendered-lang=\"cpp\"><span class=\"hljs-keyword\">int<\/span> n,m,T,tmp;\r\n<span class=\"hljs-keyword\">int<\/span> cnt[<span class=\"hljs-number\">4000005<\/span>],dis[<span class=\"hljs-number\">4000005<\/span>],dp[<span class=\"hljs-number\">4000005<\/span>];\r\n<span class=\"hljs-function\"><span class=\"hljs-title\">int main<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\r\n\tn=read(),m=read();\r\n\t<span class=\"hljs-keyword\">for<\/span>(<span class=\"hljs-keyword\">int<\/span> i=<span class=\"hljs-number\">1<\/span>; i&lt;=n; i++)\r\n\t\ttmp=read(),T=max(T,tmp),cnt[tmp]++,dis[tmp]+=tmp;\r\n\t<span class=\"hljs-keyword\">for<\/span>(<span class=\"hljs-keyword\">int<\/span> i=<span class=\"hljs-number\">1<\/span>; i&lt;m+T; i++)cnt[i]+=cnt[i<span class=\"hljs-number\">-1<\/span>],dis[i]+=dis[i<span class=\"hljs-number\">-1<\/span>];\r\n\t<span class=\"hljs-keyword\">for<\/span>(<span class=\"hljs-keyword\">int<\/span> i=<span class=\"hljs-number\">0<\/span>; i&lt;m+T; i++) {\r\n\t\tdp[i]=cnt[i]*i-dis[i];\r\n\t\t<span class=\"hljs-keyword\">for<\/span>(<span class=\"hljs-keyword\">int<\/span> j=i<span class=\"hljs-number\">-2<\/span>*m&gt;<span class=\"hljs-number\">0<\/span>?i<span class=\"hljs-number\">-2<\/span>*m:<span class=\"hljs-number\">0<\/span>; j&lt;=i-m; j++)\/\/\u6b64\u5904\u9632\u6b62\u5de6\u8fb9\u754c\u8d8a\u754c\r\n\t\t\tdp[i]=min(dp[i],dp[j]+(cnt[i]-cnt[j])*i-dis[i]+dis[j]);\r\n\t}\r\n\ttmp=<span class=\"hljs-number\">0x7ffffff<\/span>;\r\n\t<span class=\"hljs-keyword\">for<\/span>(<span class=\"hljs-keyword\">int<\/span> i=T; i&lt;m+T; i++)tmp=min(tmp,dp[i]);\r\n\t<span class=\"hljs-keyword\">return<\/span> !<span class=\"hljs-built_in\">printf<\/span>(<span class=\"hljs-string\">\"%d\"<\/span>,tmp);\r\n}<\/code>*\/<\/code><\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u5c06\u65f6\u95f4\u62bd\u8c61\u4e3a\u4e00\u6839\u6570\u8f74\uff0c\u5c06\u5176\u5206\u4e3ak\u6bb5\uff0c\u6bcf\u4e00\u6bb5\u4e2d\u7684\u53f3\u7aef\u70b9\u8868\u793a\u5f53\u524d\u7aef\u70b9\u53d1\u4e86\u4e00\u73ed\u8f66\uff0c\u6b64\u65f6t&lt;=i\u7684\u65c5\u5ba2\u5747\u53ef\u4e0a\u8f66\u3002 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-603","post","type-post","status-publish","format-standard","hentry","category-cpp"],"_links":{"self":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/603","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=603"}],"version-history":[{"count":3,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/603\/revisions"}],"predecessor-version":[{"id":608,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/603\/revisions\/608"}],"wp:attachment":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=603"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=603"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=603"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}