{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"给出N个单词,每个单词有个非负权值Ci,现在要将它们分成连续的若干段,每段的代价为此段单词的权值和的平方,还要加一个常数M,即\u003cimg style\u003d\"width:62px;height:34px;\" src\u003d\"CDN_BASE_URL/deb59af46e26501d1335903fa890b00f?v\u003d1531833291\" SRC\u003d\"CDN_BASE_URL/deb59af46e26501d1335903fa890b00f?v\u003d1531833291\"\u003e。现在想求出一种最优方案,使得总费用之和最小。"}},{"title":"输入格式","value":{"format":"MD","content":"包含多组测试数据,对于每组测试数据。\n第一行包含两个整数N和M(0\u003c\u003dN\u003c\u003d500000,0\u003c\u003dM\u003c\u003d1000)。\n第2-N+1行为N个整数。"}},{"title":"输出格式","value":{"format":"MD","content":"输出仅一个整数,表示最小的价值。"}},{"title":"样例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 10\n1\n2\n5\n2\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e80\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"知识点","value":{"format":"MD","content":"![斜率优化DP 打印文章.png](https://s2.loli.net/2023/09/01/HWAkfBuM3pib9X2.png)\n![斜率优化DP 打印文章2.png](https://s2.loli.net/2023/09/01/roOdzymaBUhvFJk.png)\n![1.png](https://s2.loli.net/2023/09/02/jsuEWozveMLkBRd.png)\n![2.png](https://s2.loli.net/2023/09/02/tIjWlixnRTGFNp8.png)\n参考视频:\nhttps://www.bilibili.com/video/BV1CM4y147Ef/?spm_id_from\u003d333.999.0.0\n```\n#include \u003ciostream\u003e\n#include \u003ccstring\u003e\n#include \u003calgorithm\u003e\nusing namespace std;\n\ntypedef long long LL;\nconst int N \u003d 500010;\nint n,m,q[N];\nLL s[N],f[N];\n\ndouble slope(int i,int j){ \n return (double)(f[i]+s[i]*s[i]-f[j]-s[j]*s[j])\n /(s[i]\u003d\u003ds[j]?1e-9:s[i]-s[j]);\n}\nint main(){\n while(~scanf(\"%d%d\",\u0026n,\u0026m)){\n for(int i\u003d1;i\u003c\u003dn;i++) scanf(\"%lld\",\u0026s[i]),s[i]+\u003ds[i-1];\n \n int h\u003d1,t\u003d0;\n for(int i\u003d1;i\u003c\u003dn;i++){\n while(h\u003ct \u0026\u0026 slope(i-1,q[t])\u003c\u003dslope(q[t],q[t-1])) t--;\n q[++t]\u003di-1; \n while(h\u003ct \u0026\u0026 slope(q[h+1],q[h])\u003c\u003d2*s[i]) h++;\n int j\u003dq[h];\n f[i]\u003df[j]+(s[i]-s[j])*(s[i]-s[j])+m;\n }\n printf(\"%lld\\n\",f[n]);\n }\n}\n```\n判断斜率不做除法做乘法:\n```\n#include \u003ciostream\u003e\n#include \u003ccstring\u003e\n#include \u003calgorithm\u003e\nusing namespace std;\n\ntypedef long long LL;\nconst int N \u003d 500010;\nint n,m,q[N];\nLL s[N],f[N];\n\nLL dy(int i,int j){return f[i]+s[i]*s[i]-f[j]-s[j]*s[j];}\nLL dx(int i,int j){return s[i]-s[j];}//注意都是大减小 保证不变号\nint main(){\n while(~scanf(\"%d%d\",\u0026n,\u0026m)){\n for(int i\u003d1;i\u003c\u003dn;i++)scanf(\"%lld\",\u0026s[i]),s[i]+\u003ds[i-1];\n\n int h\u003d1,t\u003d0;\n for(int i\u003d1;i\u003c\u003dn;i++){\n while(h\u003ct \u0026\u0026 dy(i-1,q[t])*dx(q[t],q[t-1])\n \u003c\u003ddx(i-1,q[t])*dy(q[t],q[t-1])) t--;\n q[++t]\u003di-1; \n while(h\u003ct \u0026\u0026 dy(q[h+1],q[h])\n \u003c\u003ddx(q[h+1],q[h])*2*s[i]) h++;\n int j\u003dq[h];\n f[i]\u003df[j]+(s[i]-s[j])*(s[i]-s[j])+m;\n }\n printf(\"%lld\\n\",f[n]);\n }\n}\n```\n"}}]}