首先根據題目中給的要求，推一下方差的柿子。

\[v\times m^2 = m\times \sum x^2 - 2 \times sum \times sum +sum*sum\]

所以\(ans = v*m^2 = m\times \sum x^2 - sum*sum\)

那我們實際上就是最大化平方和。

由于題目限制了要分\(m\)段。所以我們的\(dp\)狀態就是\(f[i][j]\)表示前\(i\)個數分了\(j\)段。
那么一個比較顯然的轉移
\(dp[i][p]=min(dp[j][p-1]+(s[i]-s[j]^2))\)

然后直接套斜率優化就好了！

但是要注意的是，因為題目中對第二維有點限制，所以我們要開\(m\)個單調隊列來維護。
對于\(dp[i][j]\)，每次從\(j-1\)的單調隊列要轉移。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<map> #include<set> #define mk make_pair #define ll long long using namespace std; inline int read() {int x=0,f=1;char ch=getchar();while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; } const int maxn = 3010; struct Point{int x,y; }; ll chacheng(Point x,Point y) {ll xx = x.x;ll yy = x.y;ll xxx = y.x;ll yyy = y.y;return xx*yyy-xxx*yy; } struct Node{Point q[maxn];int head=1,tail=0;bool count(Point i,Point j,Point k){Point x,y;x.x=k.x-i.x;x.y=k.y-i.y;y.x=k.x-j.x;y.y=k.y-j.y;if (chacheng(x,y)<=0ll) return true;return false;}void push(Point x){while (tail>=head+1 && count(q[tail-1],q[tail],x)) tail--;q[++tail]=x;}void pop(int lim){while (tail>=head+1 && q[head+1].y-q[head].y<lim*(q[head+1].x-q[head].x)) head++;} }; Node q[maxn]; int sum[maxn]; int n,m; int dp[maxn][maxn]; int main() {n=read();m=read();for (int i=1;i<=n;i++) sum[i]=read();for (int i=1;i<=n;i++) sum[i]+=sum[i-1];for (int i=0;i<=n;i++) q[i].push((Point){0,0});for (int i=1;i<=n;i++){for (int j=1;j<=min(i,m);j++){q[j-1].pop(2*sum[i]);Point now = q[j-1].q[q[j-1].head];dp[i][j]=now.y-now.x*now.x + (sum[i]-now.x)*(sum[i]-now.x);q[j].push((Point){sum[i],dp[i][j]+sum[i]*sum[i]});}}//cout<<dp[n][m]<<" "<<m<<" "<<sum[n]*sum[n]<<endl;cout<<dp[n][m]*m-sum[n]*sum[n]<<endl;return 0; }

轉載于:https://www.cnblogs.com/yimmortal/p/10178961.html

總結

以上是生活随笔為你收集整理的洛谷4072 SDOI2016征途 （斜率优化+dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。