「SDOI2016」征途 题解

「SDOI2016」征途

先浅浅复制一个方差

显然dp，可以搞一个🦁

dp[i][j]dp[i][j]为前i段路程j天到达的最小方差

开始暴力转移

dp[i][j]=min(dp[k][j−1]+?)(j−1≤k≤i−1)dp[i][j]=min(dp[k][j−1]+?)(j−1≤k≤i−1)这咋写？还是需要转换一下🦁

开始了，but题目的方差还需要✖m^2,很好

以下x为m天行走的平均值，s[i]为1~i段路的总路程

那么x可以算对吧:x=s[n]mx=s[n]m

m×m∑i=1(xi−x)2=m×m∑i=1(x2i+x2−2xxi)=m×(m∑i=1x2i+m∑i=1x2−m∑i=12xxi)=m×(m∑i=1x2i+s[n]2m−2s[n]mm∑i=1xi)=m×(m∑i=1x2i+s[n]2m−2s[n]2m)=m×(m∑i=1x2i−s[n]2m)=m×m∑i=1x2i−s[n]2

是不是感觉快完了推🦁真爽

所以我们似乎只需要维护∑mi=1x2i最小就好了！

重新定义dp[i][j]为前i段路程分j天到达的每天路程平方的和的最小值

最后答案就应该是dp[n][m]×m−s[n2]

好，开始看状态转移

dp[i][j]=min(dp[k][j−1]+(s[i]−s[k])2)(j−1≤k≤i−1)很简单的状态转移，但是复杂度n3不接受，好像只有n2可以的样子（带log的方法就别杠）

那怎么优化？

我们发现好像是跟s[i]∗s[k]有关，不能直接单调队列，那斜率优化吧！

dp[i][j]=dp[k][j−1]+(s[i]−s[k])2dp[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])(dp[k1][j−1]+s[k1]2)−(dp[k2][j−1]+s[k2]2)(s[k1]−s[k2])<2s[i]

因为是小于，所以是下凸壳，然后就完了噢！

呼，公式真难打

#include
#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+1y(j,q[head+1])-y(j,q[head])
			<=2*s[i]*(s[q[head+1]]-s[q[head]]))head++;
			if(headint k=q[head];
				f[i][j]=f[k][j-1]+db(s[i]-s[k]);
			}
			while(head+1y(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;
}
折叠