征途这是一道十分经典的斜率优化
我们可以从题目中的方差来想,也就很容易的到这个式子
[ans=m^2*frac{sum_{i=1}^{m}{(x_i-{overline{x}})^2}}{m}
]
化简就会得到
[ans=m*sum_{i=1}^{m}{(x_i-{overline{x}})^2}
]
在化简得
[ans={m*sum_{i=1}^{m}{x_i}^2}+{sum_{i=1}^{m}{x_i}}
]
经过观察，我们可以很容易发现(sum_{i=1}^{m}{x_i})是定值，同时(m*sum_{i=1}^{m}{x_i}^2)中的(m)也是定值，所以我们的目标就是让(sum_{i=1}^{m}{{x_i}^2})最小
我们令(dp[i][j]=min{dp[i-1][j-k]+(sum[j]-sum[j-k])^2})
其中我们令(sum[i]=sum_{k=1}^{i}{val_k})
其中(val_k)是第k段路的长度
由此我们就可得到一个开o2可以卡成80的代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
long long n,m,dp[3001][3001],sum[3001];
const int BufferSize=100*1000;
char buffer[BufferSize],*head,*tail;
bool not_EOF=true;
inline char Getchar(){
if(not_EOF and head==tail){
int len=fread(buffer,1,BufferSize,stdin);
not_EOF=len!=0;
head=buffer,tail=head+len;
}
return not_EOF?*head++:-1;
}
inline long long rd(){
long long x=0,s=1;
char c=Getchar();
for(;!isdigit(c) and not_EOF;c=Getchar()) if(c=='-') s=-1;
for(; isdigit(c) and not_EOF;c=Getchar()) x=(x<<1)+(x<<3)+(c^48);
return s*x;
}
inline void scan(char *str){
char c=Getchar();
for(; isspace(c) and not_EOF;c=Getchar());
for(;!isspace(c) and not_EOF;c=Getchar()) *(str++)=c;
*str=0;
}
int main(){
memset(dp,0x7f,sizeof(dp));
n=rd(),m=rd();
for(int i=1;i<=n;i++){
long long x=rd();
sum[i]=sum[i-1]+x;
}
dp[0][0]=-sum[n]*sum[n];
for(int i=0;i<m;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=n-j;k++){
dp[i+1][j+k]=min(dp[i+1][j+k],dp[i][j]+(sum[j+k]-sum[j])*(sum[j+k]-sum[j])*m);
}
}
}
printf("%lld",dp[m][n]);
return 0;
}
但是我们可以发现这个代码是(O(nm))的，显然我是不可以接受的。其实我们可以很容易证明这个的决策单调性，于是我们就可以用斜率优化
我们令(y<x<i)
因为决策单调性，所以对于决策(i)时，k转移必定比j转移要优，我们就可以得到这么一个式子
[dp[i-1][x]+(sum[j]-sum[x])^2<dp[i-1][y]+(sum[j]-sum[y])^2
]
化简得
[frac{(dp[i-1][x]+sum[x]^2)-(dp[i-1][y]+sum[y]^2)}{sum[x]-sum[y]}<2*sum[j]
]
这样我们就可以用斜率又花了
我们把(p_1(dp[i-1][x]+sum[x]^2,sum[x]))和(p_2(dp[i-1][y]+sum[y]^2,sum[y]))看做(p_1,p_2)两个点，刚刚那个式子也就是它们所连线的斜率表达式
我们也就可以得到这样的代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long n,m,dp[3001][3001],sum[3001];
int q[3001];
double getpoint(int i,int p){return (double)dp[i][p]+sum[i]*sum[i];}
double slope(int j,int k,int p){return (double)(getpoint(j,p)-getpoint(k,p))/(double)(sum[j]-sum[k]);}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
long long x;
scanf("%lld",&x);
sum[i]=sum[i-1]+x;
dp[i][1]=sum[i]*sum[i];
}
for(int k=2;k<=m;k++){
int head=1,tail=0;
for(int i=1;i<=n;i++){
while(head<tail and slope(q[head],q[head+1],k-1)<2*sum[i])head++;
int j=q[head];
dp[i][k]=dp[j][k-1]+(sum[j]-sum[i])*(sum[j]-sum[i]);
while(head<tail and slope(q[tail],q[tail-1],k-1)>slope(q[tail],i,k-1))tail--;
q[++tail]=i;
}
}
printf("%lld",m*dp[n][m]-sum[n]*sum[n]);
return 0;
}