{"id":634,"date":"2019-02-20T21:33:13","date_gmt":"2019-02-20T13:33:13","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=634"},"modified":"2019-02-20T21:33:13","modified_gmt":"2019-02-20T13:33:13","slug":"lp3648-apio2014-%e5%ba%8f%e5%88%97%e5%88%86%e5%89%b2","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2019\/02\/20\/lp3648-apio2014-%e5%ba%8f%e5%88%97%e5%88%86%e5%89%b2\/","title":{"rendered":"lp3648 APIO2014 \u5e8f\u5217\u5206\u5272"},"content":{"rendered":"\n

\u9996\u5148\u8bc1\u660e\u5e8f\u5217\u5206\u5272\u7684\u6b21\u5e8f\u548c\u6700\u540e\u7684\u7b54\u6848\u6beb\u65e0\u5173\u7cfb\u3002
\n\u8fd9\u53ef\u4ee5\u7528\u4e58\u6cd5\u7684\u57fa\u672c\u6027\u8d28\u8bc1\u660e\u3002\u4f8b\u5982\u5206\u6210\u4e09\u6bb5\uff0c\u6211\u4eec\u6709\uff1a
\n$$a(b+c)+bc=b(a+c)+ac$$<\/p>\n\n\n\n

\u6211\u4eec\u53ef\u4ee5\u8fdb\u884cDP\u3002
\n\u6211\u4eec\u8bb0\\(f_{i,k}\\)\u8868\u793a\u5f53\u524d\u8bbf\u95ee\u5230\u7b2c\\(i\\)\u4e2a\u70b9\uff0c\u4f7f\u7528\u4e86\\(k\\)\u6b21\u5207\u5272\u7684\u7b54\u6848\u3002
\n\u90a3\u4e48\u6839\u636e\u9898\u76ee\u4e2d\u8d21\u732e\u7684\u5b9a\u4e49\uff0c\u6211\u4eec\u6709\uff1a
\n$$f_{i,k}=max_{j=k}^{i-1}{f_{j,k-1}+sm_{j}(sm_{i}-sm_{j})}$$\n\u4ee4\\(k\\le j_1(sm_i-sm_{j_1})\\le f_{j_2,k-1}+sm_{j_2}(sm_i-sm_{j_2})\\)$\n\u5c55\u5f00\uff0c\u79fb\u9879\uff0c\u5408\u5e76\u3002\n$$f_{j_1,k-1}+sm_{j_1}sm_i-sm_{j_1}^2\\le f_{j_2,k-1}+sm_{j_2}sm_i-sm_{j_2}^2$$\n$$f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2\\le sm_{j_2}sm_i-sm_{j_1}*sm_i$$
\n$$\\frac{f_{j_1,k-1}-f_{j_2,k-1}+sm_{j_2}^2-sm_{j_1}^2}{sm_{j_2}-sm_{j_1}}\\le sm_i$$
\n\u8fd9\u4e2a\u5f0f\u5b50\u663e\u7136\u662f\u53ef\u4ee5\u659c\u7387\u4f18\u5316\u7684\u3002
\n\u8fd9\u6837\u505a\u7684\u65f6\u7a7a\u590d\u6742\u5ea6\u662f\\(O(nk)\\)\u7684\u3002
\n\u8003\u8651\u5230\u8fd9\u4e00\u9898\u7684\u7a7a\u95f4\u9650\u5236\u6bd4\u8f83\u7d27\u5f20\uff0c\u6211\u4eec\u53ef\u4ee5\u7528\u6eda\u52a8\u6570\u7ec4\u628a\\(k\\)\u8fd9\u4e00\u7ef4\u538b\u6389\u3002 <\/em><\/p>\n\n\n\n

#include<iostream>\n#include<cstdio>\n\nint q[100005];\nlong long f[100005][2],sm[100005];\nint ans[100005][205],n,K;\ninline double slope(int j1,int j2,int k){\n\treturn (sm[j1]^sm[j2])?(double)(f[j1][(k&1)^1]-f[j2][(k&1)^1]+sm[j2]*sm[j2]-sm[j1]*sm[j1])\/(double)(sm[j2]-sm[j1]):-1E18;\n} \nvoid init(){\n\tscanf(\"%d%d\",&n,&K);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%lld\",&sm[i]);\n\t\tsm[i]+=sm[i-1];\n\t}\n\tfor(int i=1;i<=K;++i){\n\t\tint l,r;\n\t\tl=r=1;\n\t\tfor(int j=1;j<=n;++j){\n\t\t\twhile(l<r&&slope(q[l],q[l+1],i)<=sm[j]){\n\t\t\t\t++l;\n\t\t\t}\n\t\t\tf[j][i&1]=f[q[l]][(i&1)^1]+sm[q[l]]*(sm[j]-sm[q[l]]);\n\t\t\tans[j][i]=q[l];\n\t\t\twhile(l<r&&slope(q[r-1],q[r],i)>slope(q[r],j,i)){\n\t\t\t\t--r;\n\t\t\t}\n\t\t\tq[++r]=j;\n\t\t}\n\t}\n\tint nw=n;\n\tprintf(\"%lld\\n\",f[n][K&1]);\n\tfor(int i=K;i>=1;--i){\n\t\tnw=ans[nw][i];\n\t\tprintf(\"%d \",nw);\n\t}\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9996\u5148\u8bc1\u660e\u5e8f\u5217\u5206\u5272\u7684\u6b21\u5e8f\u548c\u6700\u540e\u7684\u7b54\u6848\u6beb\u65e0\u5173\u7cfb\u3002 \u8fd9\u53ef\u4ee5\u7528\u4e58\u6cd5\u7684\u57fa\u672c\u6027\u8d28\u8bc1\u660e\u3002\u4f8b\u5982\u5206\u6210\u4e09\u6bb5\uff0c\u6211\u4eec\u6709\uff1a $$a(b+ … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201clp3648 APIO2014 \u5e8f\u5217\u5206\u5272\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[18,34,88,8,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/634"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=634"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/634\/revisions"}],"predecessor-version":[{"id":635,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/634\/revisions\/635"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=634"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=634"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=634"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}