loj2035 「SDOI2016」征途

学了斜率优化这题就能一气呵成地做出来啦qwqqwq

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, m, x[3005], s[3005], l, r, dp[3005][3005], que[3005];

double getK(int j, int u, int v){

	return (double)(dp[v][j-1]+s[v]*s[v]-(dp[u][j-1]+s[u]*s[u]))/(s[v]-s[u]);

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=n; i++){

		scanf("%d", &x[i]);

		s[i] = s[i-1] + x[i];

	}

	for(int i=1; i<=n; i++)

		dp[i][1] = s[i] * s[i];

	for(int j=2; j<=m; j++){

		l = r = 0;

		for(int i=1; i<=n; i++){

			while(l<r && getK(j,que[l],que[l+1])<2*s[i])	l++;

			dp[i][j] = dp[que[l]][j-1] + (s[i] - s[que[l]]) * (s[i] - s[que[l]]);

			while(l<r && getK(j,que[r-1],que[r])>=getK(j,que[r],i))	r--;

			que[++r] = i;

		}

	}

	cout<<m*dp[n][m]-s[n]*s[n]<<endl;

	return 0;

}