{"id":798,"date":"2019-01-07T19:35:45","date_gmt":"2019-01-07T11:35:45","guid":{"rendered":"https:\/\/mnihyc.tk\/blog\/?p=798"},"modified":"2020-02-09T03:11:06","modified_gmt":"2020-02-08T19:11:06","slug":"cf868-f-yet-another-minimization-problem","status":"publish","type":"post","link":"https:\/\/0.mnihyc.com\/blog\/archives\/798","title":{"rendered":"[CF868-F] Yet Another Minimization Problem"},"content":{"rendered":"<h1 style=\"text-align: center;\">[CF868-F] Yet Another Minimization Problem<\/h1>\n<p style=\"text-align: center;\">\u65f6\u95f4\u9650\u5236\uff1a1000MS \u5185\u5b58\u9650\u5236\uff1a262144KB<\/p>\n<p style=\"text-align: center;\">\u96be\u5ea6\uff1a<span style=\"color: #ff9900;\">\\(6.0\\)<\/span><\/p>\n<ul>\n<li>\n<h3><strong>\u9898\u76ee\u63cf\u8ff0<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u6709 \\(n\\) \u4e2a\u6b63\u6574\u6570\u6784\u6210\u5e8f\u5217 \\(a\\) \uff0c\u5b9a\u4e49\u4e00\u4e2a\u533a\u95f4 \\([l, r]\\) \u7684\u4ee3\u4ef7\u4e3a \u6ee1\u8db3 \\(l \\leq i, j \\leq r\\) \u5e76\u4f7f\u5f97 \\(a_i=a_j\\) \u7684\u65e0\u5e8f\u5bf9 \\([i, j]\\) \u7684\u6570\u91cf\u3002<\/p>\n<p>\u73b0\u8981\u628a \\(a\\) \u5206\u6210 \\(k\\) \u4e2a\u4e92\u4e0d\u76f8\u4ea4\u4e14\u4e0d\u4e3a\u7a7a\u7684\u8fde\u7eed\u7684\u533a\u95f4\uff0c\u6c42\u51fa\u5728\u6240\u6709\u5206\u6cd5\u4e2d\uff0c\u5206\u51fa\u533a\u95f4\u7684<strong>\u6700\u5c0f\u4ee3\u4ef7\u548c<\/strong>\u662f\u591a\u5c11\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u8f93\u5165\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u7b2c\u4e00\u884c\uff0c\u4e24\u4e2a\u6b63\u6574\u6570 \\(n, k\\) \u3002<\/p>\n<p>\u7b2c\u4e8c\u884c\uff0c\u5e8f\u5217 \\(a\\) \uff0c\u5171 \\(n\\) \u4e2a\u5143\u7d20\uff0c\u7528\u4e00\u4e2a\u7a7a\u683c\u9694\u5f00\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u8f93\u51fa\u683c\u5f0f<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a\u5728\u6240\u6709\u5206\u6cd5\u4e2d\uff0c\u5206\u51fa\u533a\u95f4\u7684\u6700\u5c0f\u4ee3\u4ef7\u548c\u3002<\/p>\n<ul>\n<li>\n<h3><strong>\u6837\u4f8b\u8f93\u5165<\/strong><\/h3>\n<\/li>\n<\/ul>\n<pre class=\"\">7 3\r\n1 1 3 3 3 2 1<\/pre>\n<ul>\n<li>\n<h3><strong>\u6837\u4f8b\u8f93\u51fa<\/strong><\/h3>\n<\/li>\n<\/ul>\n<pre class=\"\">1<\/pre>\n<ul>\n<li>\n<h3><strong>\u6837\u4f8b\u8bf4\u660e<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u4e00\u79cd\u53ef\u80fd\u7684\u5206\u6cd5\u4e3a \\([1], [1, 3], [3, 3, 2, 1]\\) \u3002<\/p>\n<p>\u7b2c\u4e00\u4e2a\u533a\u95f4\u7684\u4ee3\u4ef7\u4e3a \\(0\\) \uff0c\u7b2c\u4e8c\u4e2a\u533a\u95f4\u7684\u4ee3\u4ef7\u4e3a \\(0\\) \uff0c\u7b2c\u4e09\u4e2a\u533a\u95f4\u7684\u4ee3\u4ef7\u4e3a \\(1\\) \uff0c\u6700\u5c0f\u4ee3\u4ef7\u548c\u4e3a \\(1\\) \u3002<\/p>\n<p>\uff08\u5176\u4ed6\u6837\u4f8b\u89c1\u539f\u9898<\/p>\n<ul>\n<li>\n<h3><strong>\u6570\u636e\u8303\u56f4<\/strong><\/h3>\n<\/li>\n<\/ul>\n<p>\u5bf9\u4e8e \\(10\\%\\) \u7684\u6570\u636e\uff0c\\(2 \\leq n \\leq 20\\) \u3002<\/p>\n<p>\u5bf9\u4e8e \\(40\\%\\) \u7684\u6570\u636e\uff0c\\(2 \\leq n \\leq 1000\\) \u3002<\/p>\n<p>\u5bf9\u4e8e \\(100\\%\\) \u7684\u6570\u636e\uff0c\\(2 \\leq n \\leq 10^5\\) \uff0c\\(2 \\leq k \\leq min\\{20,n\\}\\) \u3002<\/p>\n<p>\u4fdd\u8bc1 \\(1 \\leq a_i \\leq n\\) \u3002<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>\\(Source\\): <a href=\"https:\/\/codeforces.com\/contest\/868\/problem\/F\" data-cke-saved-href=\"https:\/\/codeforces.com\/contest\/868\/problem\/F\">CF868-F <\/a><\/p>\n<p><!--more--><\/p>\n<hr \/>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>\u8bbe \\(f_{i, j}\\) \u4e3a\u505a\u5230\u7b2c \\(i\\) \u4e2a\u6570\uff0c<strong>\\(1\\) ~ \\(i\\) \u4e2d\u5206\u4e86 \\(j\\) \u6bb5<\/strong>\u7684<strong>\u6700\u5c0f\u4ee3\u4ef7<\/strong>\u3002<\/p>\n<p>\u6240\u4ee5 \\(f_{i,j}=\\min\\limits_{k=1}^{i-1}\\{f_{k,j-1}+w_{k,i}\\}\\) \uff0c \\(w_{k, i}\\) \u8868\u793a <strong>\\([k+1, i]\\) \uff08\u6ce8\u610f\u8303\u56f4\uff09 <\/strong>\u4e3a\u4e00\u6bb5\u7684\u4ee3\u4ef7\uff08\u4e24\u4e24\u76f8\u540c\u7684\u6570\u7684<strong>\u65e0\u5e8f\u5bf9\u5bf9\u6570<\/strong>\uff09\uff0c\u53d1\u73b0 \\(j\\) \u8fd9\u4e00\u7ef4\u53ef\u4ee5\u76f4\u63a5<strong>\u6eda\u52a8<\/strong>\u6389<del>\uff08\u4e0d\u6eda\u52a8\u5176\u5b9e\u4e5f\u6ca1\u4ec0\u4e48www\uff09<\/del>\u3002<\/p>\n<p>\u5c31\u53d8\u6210\u4e86 \\(g_i=\\min\\limits_{k=1}^{i-1}\\{f_k+w_{k,i}\\}\\) \uff0c\u65f6\u95f4\u590d\u6742\u5ea6 \\(O(n^2k)\\) \u65e0\u6cd5\u901a\u8fc7\u672c\u9898\u3002<\/p>\n<pre class=\"minimize:true lang:default decode:true\">#include &lt;cstdio&gt;\r\n#include &lt;cstdlib&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;climits&gt;\r\n\r\n#define _min(_a,_b) ((_a)&lt;(_b)?(_a):(_b))\r\n\r\ninline int getnum()\r\n{\r\n\tregister char c=getchar();\r\n\twhile(!(c&gt;='0' &amp;&amp; c&lt;='9'))\r\n\t\tc=getchar();\r\n\tregister int a=0;\r\n\twhile(c&gt;='0' &amp;&amp; c&lt;='9')\r\n\t{\r\n\t\ta*=10;a+=c-'0';\r\n\t\tc=getchar();\r\n\t}\r\n\treturn a;\r\n}\r\n\r\nint a[105050],cnt[105050],xf;\r\nlong long f[2][105050],w;\r\n\r\n#define _add(_a) (w+=cnt[_a]++)\r\n#define _del(_a) (w-=--cnt[_a])\r\n\r\nint main()\r\n{\r\n\tregister int N=getnum(),K=getnum();\r\n\tfor(register int i=1;i&lt;=N;i++)\r\n\t\ta[i]=getnum();\r\n\t\r\n\tw=0;\r\n\tfor(register int i=1;i&lt;=N;i++)\r\n\t\tf[0][i]=_add(a[i]);\r\n\tmemset(cnt,0,sizeof(cnt));w=0;\r\n\tfor(register int j=2;j&lt;=K;j++)\r\n\t{\r\n\t\txf^=1;\r\n\t\tmemset(&amp;f[xf],0x3F,sizeof(f[xf]));\r\n\t\tfor(register int i=1;i&lt;=N;i++)\r\n\t\t{\r\n\t\t\tfor(register int k=1;k&lt;=i;k++)\r\n\t\t\t\t_add(a[k]);\r\n\t\t\tfor(register int k=1;k&lt;i;k++)\r\n\t\t\t\t_del(a[k]),f[xf][i]=_min(f[xf][i],f[xf^1][k]+w);\r\n\t\t\t_del(a[i]);\r\n\t\t}\r\n\t}\r\n\tprintf(\"%lld\\n\",f[xf][N]);\r\n\t\r\n\treturn 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<hr \/>\n<p>\uff08\u6ce8\uff1a\u8bb0<strong>\u4e00\u6bb5\u533a\u95f4\u5185<\/strong>\u76f8\u540c\u7684\u6570\u7684\u65e0\u5e8f\u5bf9\u5bf9\u6570\u53ef\u4ee5\u65b9\u4fbf\u5730\u5f00\u4e00\u4e2a\u6876\uff0c\u589e\u52a0\u4e00\u4e2a\u5143\u7d20 \\(a\\) \u8868\u793a <code>w+=cnt[a]++;<\/code> \uff0c\u5220\u9664\u4e00\u4e2a\u5143\u7d20 \\(a\\) \u8868\u793a <code>w-=--cnt[a];<\/code> \uff0c\u56e0\u4e3a\u76f8\u540c\u5143\u7d20 \\(a\\) \u7684\u65e0\u5e8f\u5bf9\u5bf9\u6570\u4e3a \\(C_{cnt_a}^2=\\frac{cnt_a(cnt_a-1)}{2} = 1+2+\\cdots+(cnt_a-1)\\) \u3002<\/p>\n<p>\uff08\u8981\u6c42 \\(w_{k, i}\\) \uff0c\u53ea\u9700\u8981\u628a \\(1\\) ~ \\(i\\) \u7684\u6240\u6709\u5143\u7d20\u5148\u52a0\u5230\u4e00\u4e2a\u53d8\u91cf \\(w\\) \u4e2d\uff0c\u7136\u540e\u4f9d\u6b21\u5220\u9664 \\(1, 2, \\cdots , i\\) \uff0c<strong>\u5220\u9664\u7b2c<\/strong><strong> \\(k\\) \u4e2a\u5143\u7d20\u540e<\/strong> \\(w\\) \u7684\u503c\u5c31\u4e3a \\(w_{k, i}\\) \u3002<\/p>\n<p>\u7ee7\u7eed\u4f18\u5316\uff0c\u540c\u65f6\u6ce8\u610f\u5230<strong>\u51b3\u7b56\u7684\u5355\u8c03\u6027<\/strong>\u3002\u5373\u5bf9\u4e8e \\(a&lt;b&lt;c&lt;d\\)\uff0c\u5982\u679c \\(c\\) \u4ece \\(b\\) \u8f6c\u79fb\u8fc7\u6765\u6bd4\u4ece \\(a\\) \u8f6c\u79fb\u8fc7\u6765\u66f4\u4f18\uff0c\u90a3\u4e48 \\(d\\) \u4ece \\(b\\) \u8f6c\u79fb\u8fc7\u6765\u4e5f\u6bd4\u4ece \\(a\\) \u8f6c\u79fb\u8fc7\u6765\u66f4\u4f18\u3002\u5373\u82e5\u6ee1\u8db3 \\({{f_b} + {w_{b,c}} \\le {f_a} + {w_{a,c}}}\\) \u90a3\u4e48\u4e00\u5b9a\u6ee1\u8db3 \\({{f_b} + {w_{b,d}} \\le {f_a} + {w_{a,d}}}\\) \u3002\u6ce8\u610f\u5230\u53ea\u8981\u6ee1\u8db3 \\(w_{b,d}-w_{b,c} \\leq w_{a,d}-w_{a,c}\\) \u90a3\u4e48\u4e0a\u9762\u7684\u7ed3\u8bba\u4e00\u5b9a\u6210\u7acb\u3002\u53d1\u73b0\u8fd9\u4e2a\u6761\u4ef6\u5176\u5b9e\u5c31\u662f\u56db\u8fb9\u5f62\u4e0d\u7b49\u5f0f \\(w_{a,c}+w_{b,d} \\leq w_{a,d}+w_{b,c}\\) \u3002<\/p>\n<p>\u5bf9\u4e8e\u672c\u9898\uff0c\u5047\u8bbe\u989c\u8272 \\(a\\) \u5206\u522b\u5728 \\((a,b]\\) \u3001 \\((b,c]\\) \u3001 \\((c,d]\\) \u4e2d\u7684\u6570\u91cf\u4e3a \\(x ,y, z\\) \u3002\u90a3\u4e48\u5c31\u6709\u5982\u4e0b\u5173\u7cfb\uff08\u5012\u63a8\uff09\uff1a<\/p>\n<p>\\(\\begin{array}{c} {w_{a,c}} + {w_{b,d}} \\le {w_{a,d}} + {w_{b,c}}\\\\ C_{x + y}^2 + C_{y + z}^2 \\le C_{x + y + z}^2 + C_y^2\\\\ \\left( {x + y} \\right)\\left( {x + y &#8211; 1} \\right) + \\left( {y + z} \\right)\\left( {y + z &#8211; 1} \\right) \\le \\left( {x + y + z} \\right)\\left( {x + y + z &#8211; 1} \\right) + \\left( {y + z} \\right)\\left( {y + z &#8211; 1} \\right)\\\\ 0 \\le xz \\end{array}\\)<\/p>\n<p>\\(0 \\leq xz\\) <s>\u90a3\u662f\u5e9f\u8bdd<\/s>\u4e00\u5b9a\u6b63\u786e\uff0c\u4e5f\u5c31\u8bc1\u660e\u4e86\u51b3\u7b56\u7684\u5355\u8c03\u6027\u3002<\/p>\n<p>\u540c\u65f6\u8fd8\u53d1\u73b0\u6b64\u9898\u7684 \\(w_{k,i}\\) \u65e0\u6cd5\u5bf9\u4e8e\u6307\u5b9a\u7684 \\(k, i\\) \u5728 \\(O(1)\\) \u65f6\u95f4\u5185\u6c42\u51fa\uff0c\u6240\u4ee5\u65e0\u6cd5\u4f7f\u7528\u51b3\u7b56\u4e8c\u5206\u6808\u7b49\u65b9\u6cd5\uff0c\u8003\u8651\u64cd\u4f5c\u662f\u5355\u8c03\u5e76\u4e14<strong>\u79bb\u7ebf<\/strong>\uff0c\u6240\u4ee5\u4f7f\u7528<strong>\u5206\u6cbb<\/strong>\u3002<\/p>\n<p>\u6c42\u89e3\u533a\u95f4\uff1a\\(|\\gets\\) \u4e4b\u524d\u5904\u7406\u7684\u4fe1\u606f \\(\\to|\\) \\(l\\frac{\\qquad\\qquad\\qquad\\downarrow^{mid}\\qquad\\qquad\\qquad}{}r\\)<\/p>\n<p>\u51b3\u7b56\u533a\u95f4\uff1a\\(kl\\frac{\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\downarrow^{k}\\qquad\\qquad\\qquad}{}kr\\)<\/p>\n<p>\u8fd9\u91cc\u4e4b\u524d\u5904\u7406\u7684\u4fe1\u606f\u4e3b\u8981\u6307 \\(w\\) \u548c \\(cnt\\) \u6570\u7ec4\u3002<\/p>\n<p>\u5f53\u524d\u6c42\u89e3\u7684\u533a\u95f4\u4e3a \\([l, r]\\) \uff0c\u800c\u6700\u4f18\u51b3\u7b56\u53ef\u80fd\u5728\u7684\u533a\u95f4\u4e3a \\([kl, kr]\\) \u3002\u5219\u5bf9\u4e8e \\(mid=\\lfloor\\frac{l+r}{2}\\rfloor\\) \uff0c\u9700\u8981\u66b4\u529b\u627e\u51fa \\([kl, min\\{mid-1, kr\\}]\\) \u4e2d\u6700\u4f18\u7684\u8f6c\u79fb\u70b9 \\(k\\) \u3002<\/p>\n<p>\u6ce8\u610f\uff0c\u4e4b\u524d\u9884\u5904\u7406\u7684\u4fe1\u606f \\(w\\) \u8868\u793a <strong>\\([kl, l)\\)<\/strong> \u8fd9\u4e00\u533a\u95f4\u7684\u4ee3\u4ef7\uff0c\u6240\u4ee5\u5728\u5bfb\u627e\u6700\u4f18\u8f6c\u79fb\u70b9\u7684\u65f6\u5019\u6309\u7167\u6734\u7d20DP\u7684\u65b9\u6cd5\u5feb\u901f\u8ba1\u7b97\u51fa\u6240\u9700\u7684 \\(w\\) \u3002\u8bb0\u5f97\u7b97\u5b8c\u540e\u8981\u590d\u539f\u3002<\/p>\n<p>\u8981\u5904\u7406 \\([l, mid)\\) \u65f6\uff0c\u5b83\u7684\u51b3\u7b56\u533a\u95f4\u4e3a \\([kl, k]\\) \u3002\u56e0\u4e3a \\(w\\) \u539f\u672c\u5c31\u8868\u793a \\([kl, l]\\) \u8fd9\u4e00\u533a\u95f4\u7684\u4ee3\u4ef7\uff0c\u6240\u4ee5\u4e0d\u9700\u8981\u52a0\u4efb\u4f55\u5904\u7406\u5373\u53ef\u76f4\u63a5\u9012\u5f52\u8fdb\u8fd9\u4e2a\u5b50\u533a\u95f4\u3002<\/p>\n<p>\u503c\u5f97\u6ce8\u610f\u7684\u662f\uff0c\u5904\u7406 \\((mid, r]\\) \u65f6\uff0c\u5b83\u7684\u51b3\u7b56\u533a\u95f4\u4e3a \\([k, kr]\\) \u3002\u5bf9\u7167\u4e0a\u9762\u7684\u7b80\u56fe\u53d1\u73b0\u6709 \\([l, k)\\) \u8fd9\u4e00\u6bb5\u4fe1\u606f\u8fd8\u672a\u5904\u7406\uff0c\u6240\u4ee5\u5148\u5904\u7406\u51fa\u5b83\u7684\u4fe1\u606f\uff0c\u7136\u540e\u5c31\u53ef\u4ee5\u9012\u5f52\u8fdb\u8fd9\u4e2a\u5b50\u533a\u95f4\u4e86\u3002\u8bb0\u5f97\u56de\u6eaf\u7684\u65f6\u5019\u590d\u539f\u3002<\/p>\n<p>\u8fd9\u6837\u5206\u6cbb\u7684\u4f18\u79c0\u590d\u6742\u5ea6 \\(O(nklogn)\\) \u5c31\u53ef\u4ee5\u901a\u8fc7\u672c\u9898\u4e86\u3002<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:default decode:true \">#include &lt;cstdio&gt;\r\n#include &lt;cstdlib&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;climits&gt;\r\n\r\n#define _min(_a,_b) ((_a)&lt;(_b)?(_a):(_b))\r\n\r\ninline int getnum()\r\n{\r\n\tregister char c=getchar();\r\n\twhile(!(c&gt;='0' &amp;&amp; c&lt;='9'))\r\n\t\tc=getchar();\r\n\tregister int a=0;\r\n\twhile(c&gt;='0' &amp;&amp; c&lt;='9')\r\n\t{\r\n\t\ta*=10;a+=c-'0';\r\n\t\tc=getchar();\r\n\t}\r\n\treturn a;\r\n}\r\n\r\nint a[105050],cnt[105050],xf;\r\nlong long f[2][105050],w;\r\n\r\n#define _add(_a) (w+=cnt[_a]++)\r\n#define _del(_a) (w-=--cnt[_a])\r\n\r\nvoid Divide(register int l,register int r,register int kl,register int kr)\r\n{\r\n\tif(l&gt;r)\r\n\t\treturn;\r\n\tregister int mid=(l+r)&gt;&gt;1,krr=_min(mid-1,kr);\r\n\tfor(register int i=l;i&lt;=mid;i++)\r\n\t\t_add(a[i]);\r\n\tregister int k=kl;\r\n\tfor(register int i=kl;i&lt;=krr;i++)\r\n\t{\r\n\t\t_del(a[i]);\r\n\t\tif(f[xf][mid]&gt;f[xf^1][i]+w)\r\n\t\t{\r\n\t\t\tf[xf][mid]=f[xf^1][i]+w;\r\n\t\t\tk=i;\r\n\t\t}\r\n\t}\r\n\tfor(register int i=kl;i&lt;=krr;i++)\r\n\t\t_add(a[i]);\r\n\tfor(register int i=l;i&lt;=mid;i++)\r\n\t\t_del(a[i]);\r\n\t\r\n\tDivide(l,mid-1,kl,k);\r\n\t\r\n\t\r\n\tfor(register int i=l;i&lt;=mid;i++)\r\n\t\t_add(a[i]);\r\n\tfor(register int i=kl;i&lt;k;i++)\r\n\t\t_del(a[i]);\r\n\t\r\n\tDivide(mid+1,r,k,kr);\r\n\t\r\n\tfor(register int i=kl;i&lt;k;i++)\r\n\t\t_add(a[i]);\r\n\tfor(register int i=l;i&lt;=mid;i++)\r\n\t\t_del(a[i]);\r\n\t\r\n}\r\n\r\nint main()\r\n{\r\n\tregister int N=getnum(),K=getnum();\r\n\tfor(register int i=1;i&lt;=N;i++)\r\n\t\ta[i]=getnum();\r\n\t\r\n\tw=0;\r\n\tfor(register int i=1;i&lt;=N;i++)\r\n\t\tf[0][i]=_add(a[i]);\r\n\tmemset(cnt,0,sizeof(cnt));w=0;\r\n\tfor(register int j=2;j&lt;=K;j++)\r\n\t{\r\n\t\txf^=1;\r\n\t\tmemset(&amp;f[xf],0x3F,sizeof(f[xf]));\r\n\t\t\/*for(register int i=1;i&lt;=N;i++)\r\n\t\t{\r\n\t\t\tfor(register int k=1;k&lt;=i;k++)\r\n\t\t\t\t_add(a[k]);\r\n\t\t\tfor(register int k=1;k&lt;i;k++)\r\n\t\t\t\t_del(a[k]),f[xf][i]=_min(f[xf][i],f[xf^1][k]+w);\r\n\t\t\t_del(a[i]);\r\n\t\t}*\/\r\n\t\tDivide(1,N,1,N);\r\n\t}\r\n\tprintf(\"%lld\\n\",f[xf][N]);\r\n\t\r\n\treturn 0;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>[CF868-F] Yet Another Minimization Problem \u65f6\u95f4\u9650\u5236\uff1a1000MS  &hellip; <a href=\"https:\/\/0.mnihyc.com\/blog\/archives\/798\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">[CF868-F] Yet Another Minimization Problem<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[41,30,38],"tags":[],"class_list":["post-798","post","type-post","status-publish","format-standard","hentry","category-proa","category-otherdp","category-partition"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.1.1 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>[CF868-F] Yet Another Minimization Problem - mnihyc&#039;s Blog<\/title>\n<meta name=\"description\" content=\"Yet Another Minimization Problem \u65f6\u95f4\u9650\u5236\uff1a1000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u6709 (n) \u4e2a\u6b63\u6574\u6570\u6784\u6210\u5e8f\u5217 (a) \uff0c\u5b9a\u4e49\u4e00\u4e2a\u533a\u95f4 () \u7684\u4ee3\u4ef7\u4e3a \u6ee1\u8db3 (l leq i, j leq r) \u5e76\u4f7f\u5f97 (a_i=a_j)\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/0.mnihyc.com\/blog\/archives\/798\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[CF868-F] Yet Another Minimization Problem - mnihyc&#039;s Blog\" \/>\n<meta property=\"og:description\" content=\"Yet Another Minimization Problem \u65f6\u95f4\u9650\u5236\uff1a1000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u6709 (n) \u4e2a\u6b63\u6574\u6570\u6784\u6210\u5e8f\u5217 (a) \uff0c\u5b9a\u4e49\u4e00\u4e2a\u533a\u95f4 () \u7684\u4ee3\u4ef7\u4e3a \u6ee1\u8db3 (l leq i, j leq r) \u5e76\u4f7f\u5f97 (a_i=a_j)\" \/>\n<meta property=\"og:url\" content=\"https:\/\/0.mnihyc.com\/blog\/archives\/798\" \/>\n<meta property=\"og:site_name\" content=\"mnihyc&#039;s Blog\" \/>\n<meta property=\"article:published_time\" content=\"2019-01-07T11:35:45+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-02-08T19:11:06+00:00\" \/>\n<meta name=\"author\" content=\"mnihyc\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@mnihyc\" \/>\n<meta name=\"twitter:site\" content=\"@mnihyc\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"mnihyc\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/798#article\",\"isPartOf\":{\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/798\"},\"author\":{\"name\":\"mnihyc\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"headline\":\"[CF868-F] Yet Another Minimization Problem\",\"datePublished\":\"2019-01-07T11:35:45+00:00\",\"dateModified\":\"2020-02-08T19:11:06+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/798\"},\"wordCount\":354,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"articleSection\":[\"6.0 ~ 7.0\",\"\u5176\u4ed6\u7c7b\u578b\",\"\u5206\u6cbb\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/0.mnihyc.com\/blog\/archives\/798#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/798\",\"url\":\"https:\/\/0.mnihyc.com\/blog\/archives\/798\",\"name\":\"[CF868-F] Yet Another Minimization Problem - mnihyc&#039;s Blog\",\"isPartOf\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#website\"},\"datePublished\":\"2019-01-07T11:35:45+00:00\",\"dateModified\":\"2020-02-08T19:11:06+00:00\",\"description\":\"Yet Another Minimization Problem \u65f6\u95f4\u9650\u5236\uff1a1000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u6709 \\\\(n\\\\) \u4e2a\u6b63\u6574\u6570\u6784\u6210\u5e8f\u5217 \\\\(a\\\\) \uff0c\u5b9a\u4e49\u4e00\u4e2a\u533a\u95f4 \\\\(\\\\) \u7684\u4ee3\u4ef7\u4e3a \u6ee1\u8db3 \\\\(l \\\\leq i, j \\\\leq r\\\\) \u5e76\u4f7f\u5f97 \\\\(a_i=a_j\\\\)\",\"breadcrumb\":{\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/798#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/0.mnihyc.com\/blog\/archives\/798\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/0.mnihyc.com\/blog\/archives\/798#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/mnihyc.com\/blog\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[CF868-F] Yet Another Minimization Problem\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#website\",\"url\":\"https:\/\/mnihyc.com\/blog\/\",\"name\":\"mnihyc&#039;s Blog\",\"description\":\"Welcome!\",\"publisher\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/mnihyc.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"zh-Hans\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751\",\"name\":\"mnihyc\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g\",\"caption\":\"mnihyc\"},\"logo\":{\"@id\":\"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[CF868-F] Yet Another Minimization Problem - mnihyc&#039;s Blog","description":"Yet Another Minimization Problem \u65f6\u95f4\u9650\u5236\uff1a1000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u6709 (n) \u4e2a\u6b63\u6574\u6570\u6784\u6210\u5e8f\u5217 (a) \uff0c\u5b9a\u4e49\u4e00\u4e2a\u533a\u95f4 () \u7684\u4ee3\u4ef7\u4e3a \u6ee1\u8db3 (l leq i, j leq r) \u5e76\u4f7f\u5f97 (a_i=a_j)","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/0.mnihyc.com\/blog\/archives\/798","og_locale":"zh_CN","og_type":"article","og_title":"[CF868-F] Yet Another Minimization Problem - mnihyc&#039;s Blog","og_description":"Yet Another Minimization Problem \u65f6\u95f4\u9650\u5236\uff1a1000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u6709 (n) \u4e2a\u6b63\u6574\u6570\u6784\u6210\u5e8f\u5217 (a) \uff0c\u5b9a\u4e49\u4e00\u4e2a\u533a\u95f4 () \u7684\u4ee3\u4ef7\u4e3a \u6ee1\u8db3 (l leq i, j leq r) \u5e76\u4f7f\u5f97 (a_i=a_j)","og_url":"https:\/\/0.mnihyc.com\/blog\/archives\/798","og_site_name":"mnihyc&#039;s Blog","article_published_time":"2019-01-07T11:35:45+00:00","article_modified_time":"2020-02-08T19:11:06+00:00","author":"mnihyc","twitter_card":"summary_large_image","twitter_creator":"@mnihyc","twitter_site":"@mnihyc","twitter_misc":{"\u4f5c\u8005":"mnihyc","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"5 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/0.mnihyc.com\/blog\/archives\/798#article","isPartOf":{"@id":"https:\/\/0.mnihyc.com\/blog\/archives\/798"},"author":{"name":"mnihyc","@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"headline":"[CF868-F] Yet Another Minimization Problem","datePublished":"2019-01-07T11:35:45+00:00","dateModified":"2020-02-08T19:11:06+00:00","mainEntityOfPage":{"@id":"https:\/\/0.mnihyc.com\/blog\/archives\/798"},"wordCount":354,"commentCount":0,"publisher":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"articleSection":["6.0 ~ 7.0","\u5176\u4ed6\u7c7b\u578b","\u5206\u6cbb"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/0.mnihyc.com\/blog\/archives\/798#respond"]}]},{"@type":"WebPage","@id":"https:\/\/0.mnihyc.com\/blog\/archives\/798","url":"https:\/\/0.mnihyc.com\/blog\/archives\/798","name":"[CF868-F] Yet Another Minimization Problem - mnihyc&#039;s Blog","isPartOf":{"@id":"https:\/\/mnihyc.com\/blog\/#website"},"datePublished":"2019-01-07T11:35:45+00:00","dateModified":"2020-02-08T19:11:06+00:00","description":"Yet Another Minimization Problem \u65f6\u95f4\u9650\u5236\uff1a1000MS \u5185\u5b58\u9650\u5236\uff1a262144KB \u96be\u5ea6\uff1a \u9898\u76ee\u63cf\u8ff0 \u6709 \\(n\\) \u4e2a\u6b63\u6574\u6570\u6784\u6210\u5e8f\u5217 \\(a\\) \uff0c\u5b9a\u4e49\u4e00\u4e2a\u533a\u95f4 \\(\\) \u7684\u4ee3\u4ef7\u4e3a \u6ee1\u8db3 \\(l \\leq i, j \\leq r\\) \u5e76\u4f7f\u5f97 \\(a_i=a_j\\)","breadcrumb":{"@id":"https:\/\/0.mnihyc.com\/blog\/archives\/798#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/0.mnihyc.com\/blog\/archives\/798"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/0.mnihyc.com\/blog\/archives\/798#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/mnihyc.com\/blog"},{"@type":"ListItem","position":2,"name":"[CF868-F] Yet Another Minimization Problem"}]},{"@type":"WebSite","@id":"https:\/\/mnihyc.com\/blog\/#website","url":"https:\/\/mnihyc.com\/blog\/","name":"mnihyc&#039;s Blog","description":"Welcome!","publisher":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/mnihyc.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"zh-Hans"},{"@type":["Person","Organization"],"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/61e167d6d591fdd20dcfee2cf848a751","name":"mnihyc","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/8d111f863afc3f98816bc96220f97077d470a96f41088de9f19530fc480f8e72?s=96&d=mm&r=g","caption":"mnihyc"},"logo":{"@id":"https:\/\/mnihyc.com\/blog\/#\/schema\/person\/image\/"}}]}},"_links":{"self":[{"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts\/798","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/comments?post=798"}],"version-history":[{"count":0,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/posts\/798\/revisions"}],"wp:attachment":[{"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/media?parent=798"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/categories?post=798"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/0.mnihyc.com\/blog\/wp-json\/wp\/v2\/tags?post=798"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}