\u4e00\u9053\u659c\u7387\u4f18\u5316\u7684\u7ecf\u5178\u4f8b\u9898\u3002
\u5bf9\u4e8e\u8fd9\u9053\u9898\uff0cDP\u5f0f\u662f\u5bb9\u6613\u5f97\u5230\u7684\uff1a
$$f_i=min\\{f_j+(\\sum_{j+1}^ia_{i}+i-j-1-L)^2\\}$$
\u524d\u7f00\u548c\u4f18\u5316\uff1a
$$f_i=min\\{f_j+(sm_i-sm_j+i-j-1-L)^2\\}$$
\u8003\u8651\u5230\u8fd9\u662f\u4e00\u4e2a\u4e0e\u53d6\u503c\u5e73\u65b9\u76f8\u5173\u7684\u5f0f\u5b50\uff0c\u5c1d\u8bd5\u7528\u659c\u7387\u4f18\u5316\u6765\u5316\u7b80\u3002
\u4ee4\uff1a
$$u_i=sm_i+i$$
$$f_i=min{f_j+(u_i-u_j-1-L)^2}$$
\u5bf9\u4e8e\u53f3\u5f0f\uff0c\u6211\u4eec\u5047\u5b9a\\(1\\le j<k<i\\)\u4e14\u4ece\\(k\\)\u8f6c\u79fb\u8f83\u4f18\u3002
\u90a3\u4e48\u6211\u4eec\u6709\uff1a
$$f_{k}+(u_{i}-u_{k}-1-L)^2\\le f_{j}+(u_{i}-u_{j}-1-L)^2$$
\u5c55\u5f00\u5e76\u79fb\u9879\u5316\u7b80\uff1a
$$2u_{i}(u_{j}-u_{k})\\le f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2$$
\u4ee4\uff1a
$$g_{i}=(u_{i}+1+L)^2$$
\u5e76\u4e0d\u59a8\u5047\u5b9a\uff1a
$$u_{j}!=u_{k}$$
\u53ef\u5f97\uff1a
$$2u_{i}\\le\\frac{f_{j}-f_{k}+(u_{j}+1+L)^2-(u_{k}+1+L)^2}{(u_{j}-u_{k})}$$
\u6545\u800c\uff0c\u82e5\u8981\u4f7f\u5f97\u7b54\u6848\u66f4\u5927\uff0c\u5219\u4e0a\u5f0f\u5fc5\u7136\u6210\u7acb\u3002
\u8003\u8651\u5230\u8fd9\u4e2a\u5f0f\u5b50\u7b26\u5408\u5355\u8c03\u961f\u5217\u7684\u6027\u8d28\uff0c\u6211\u4eec\u53ef\u4ee5\u4e0a\u4e00\u4e2a\u7c7b\u4f3c\u5355\u8c03\u961f\u5217\u7684\u6570\u636e\u7ed3\u6784\u6765\u7ef4\u62a4\u53f3\u4fa7\u7684\u5f0f\u5b50\uff0c\u4e5f\u5c31\u662f\u4fd7\u79f0\u7684\u201c\u659c\u7387\u201d\u3002
\u8fd9\u5c31\u5b8c\u6210\u4e86\u659c\u7387\u4f18\u5316\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<queue>\n\n\nint n,L;\ndouble sm[50005],f[50005];\nint q[50005],l,r;\ninline double u(int X){\n\treturn sm[X]+X;\n}\ninline double g(int X){\n\treturn u(X)+L+1;\n}\ninline double x(int X){\n\treturn g(X);\n}\ninline double y(int X){\n\treturn f[X]+g(X)*g(X);\n}\ninline double k(int A,int B){\n\treturn (y(A)-y(B))\/(x(A)-x(B));\n}\n\nvoid init(){\n\tscanf(\"%d%d\",&n,&L);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%lf\",&sm[i]);\n\t\tsm[i]+=sm[i-1];\n\t}\n\tl=r=1;\n\tfor(int i=1;i<=n;++i){\n\t\twhile(l<r&&k(q[l],q[l+1])<2*u(i)){\n\t\t\t++l; \n\t\t} \n\t\tf[i]=f[q[l]]+(u(i)-g(q[l]))*((u(i)-g(q[l])));\n\t\twhile(l<r&&k(i,q[r-1])<k(q[r-1],q[r])){\n\t\t\t--r;\n\t\t}\n\t\tq[++r]=i;\n\t}\n\tprintf(\"%lld\\n\",(long long)f[n]);\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u9053\u659c\u7387\u4f18\u5316\u7684\u7ecf\u5178\u4f8b\u9898\u3002 \u5bf9\u4e8e\u8fd9\u9053\u9898\uff0cDP\u5f0f\u662f\u5bb9\u6613\u5f97\u5230\u7684\uff1a $$f_i=min\\{f_j+(\\sum_{j+1 … <\/p>\n