「SDOI2016」征途 題解
「SDOI2016」征途
先淺淺複製一個方差
顯然dp，可以搞一個🦁
\(dp[i][j]\)為前i段路程j天到達的最小方差
開始暴力轉移
\(dp[i][j]=min(dp[k][j-1]+?)(j-1\leq k\leq i-1)\)這咋寫？還是需要轉換一下🦁
開始了，but題目的方差還需要✖m^2,很好
以下x為m天行走的平均值，s[i]為1~i段路的總路程
那麼x可以算對吧:\(x=\frac{s[n]}{m}\)
\[m\times \sum^m_{i=1}(x_i-x)^2\\
=m\times \sum^m_{i=1}(x_i^2+x^2-2xx_i)\\
=m\times (\sum^m_{i=1}x_i^2+\sum^m_{i=1}x^2-\sum^m_{i=1}2xx_i)\\
=m\times (\sum^m_{i=1}x_i^2+\frac{s[n]^2}{m}-\frac{2s[n]}{m}\sum^m_{i=1}x_i)\\
=m\times (\sum^m_{i=1}x_i^2+\frac{s[n]^2}{m}-\frac{2s[n]^2}{m})\\
=m\times (\sum^m_{i=1}x_i^2-\frac{s[n]^2}{m})\\
=m\times \sum^m_{i=1}x_i^2-s[n]^2
\]
=m\times \sum^m_{i=1}(x_i^2+x^2-2xx_i)\\
=m\times (\sum^m_{i=1}x_i^2+\sum^m_{i=1}x^2-\sum^m_{i=1}2xx_i)\\
=m\times (\sum^m_{i=1}x_i^2+\frac{s[n]^2}{m}-\frac{2s[n]}{m}\sum^m_{i=1}x_i)\\
=m\times (\sum^m_{i=1}x_i^2+\frac{s[n]^2}{m}-\frac{2s[n]^2}{m})\\
=m\times (\sum^m_{i=1}x_i^2-\frac{s[n]^2}{m})\\
=m\times \sum^m_{i=1}x_i^2-s[n]^2
\]
是不是感覺快完了推🦁真爽
所以我們似乎只需要維護\(\sum^m_{i=1}x_i^2\)最小就好了！
重新定義\(dp[i][j]\)為前i段路程分j天到達的每天路程平方的和的最小值
最後答案就應該是\(dp[n][m]\times m-s[n^2]\)
好，開始看狀態轉移
\(dp[i][j]=min(dp[k][j-1]+(s[i]-s[k])^2)(j-1\leq k\leq i-1)\)很簡單的狀態轉移，但是複雜度\(n^3\)不接受，好像只有\(n^2\)可以的樣子（帶\(log\)的方法就別杠）
那怎麼優化？
我們發現好像是跟\(s[i]*s[k]\)有關，不能直接單調隊列，那斜率優化吧！
\[dp[i][j]=dp[k][j-1]+(s[i]-s[k])^2\\
dp[i][j]=dp[k][j-1]+s[i]^2+s[k]^2-2s[i]s[k]\\
dp[k][j-1]+s[k]^2=2s[i]s[k]-s[i]^2-dp[i][j]\\
\]
dp[i][j]=dp[k][j-1]+s[i]^2+s[k]^2-2s[i]s[k]\\
dp[k][j-1]+s[k]^2=2s[i]s[k]-s[i]^2-dp[i][j]\\
\]
點為\((s[k],dp[k][j-1]+s[k]^2)\),斜率就是\(2s[i]\)
然後就是愉快的判斷是撒子凸殼的時候了，剛學的
假設k1>k2，並且k1優於k2
\[dp[k1][j-1]+s[i]^2+s[k1]^2-2s[i]s[k1]<dp[k2][j-1]+s[i]^2+s[k2]^2-2s[i]s[k2]\\
dp[k1][j-1]+s[k1]^2-dp[k2][j-1]-s[k2]^2<2s[i](s[k1]-s[k2])\\
\frac {(dp[k1][j-1]+s[k1]^2)-(dp[k2][j-1]+s[k2]^2)}{(s[k1]-s[k2])}<2s[i]
\]
dp[k1][j-1]+s[k1]^2-dp[k2][j-1]-s[k2]^2<2s[i](s[k1]-s[k2])\\
\frac {(dp[k1][j-1]+s[k1]^2)-(dp[k2][j-1]+s[k2]^2)}{(s[k1]-s[k2])}<2s[i]
\]
因為是小於，所以是下凸殼，然後就完了噢！
呼，公式真難打
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3010;
int a[maxn];
ll f[maxn][maxn],s[maxn];
ll db(ll x){
return x*x;
}
int n,m;
ll y(int j,int k){
return f[k][j-1]+db(s[k]);
}
int q[maxn],head,tail=1;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
f[i][1]=s[i]*s[i];
}
//以後最後都把第一種情況初始化了！！！！不然調用空的就容易錯
for(int j=2;j<=m;j++){//注意j為1也就是只分成一段的情況的初始化！！是s[i]*s[i]!!!!!!
tail=head=0;
q[tail++]=j-1;
for(int i=j;i<=n;i++){
while(head+1<tail&&y(j,q[head+1])-y(j,q[head])
<=2*s[i]*(s[q[head+1]]-s[q[head]]))head++;
if(head<tail){
int k=q[head];
f[i][j]=f[k][j-1]+db(s[i]-s[k]);
}
while(head+1<tail&&(y(j,q[tail-1])-y(j,q[tail-2]))*(s[i]-s[q[tail-1]])
>=(y(j,i)-y(j,q[tail-1]))*(s[q[tail-1]]-s[q[tail-2]]))tail--;
q[tail++]=i;
}
}
printf("%lld",f[n][m]*m-db(s[n]));
return 0;
}
