C++(g++ 7.5.0) 解法, 执行用时: 132ms, 内存消耗: 96340K, 提交时间: 2022-09-04 16:32:08

#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
#include<set>
#include<map>
#include<stack>
#include<algorithm>
#include<sstream>
#include<math.h>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define dream return 0;
ll dp[3500][3500];//用了i天,到达前j个地方
ll a[3005];//第i段的距离
ll tot[3005];
ll q[3500];//队列
void solve()
{
	ll n, m;
	cin >> n >> m;
	ll sum = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		sum += a[i];
		tot[i] = tot[i - 1] + a[i];
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	ll temp = sum * sum;
	ll hh = 0;
	ll tt = 0;
	//cout << m * dp[m][n] - temp << endl;
	//cout << "dwa" << endl;
	//dp[i][j]-tot[i]^2+2*tot[i]*tot[k]=dp[k][j-1]+tot[k]^2; b+k*x=y;
	//b=dp[i][j]-tot[i]^2
	//k=2*tot[i]
	//x=tot[k]
	//y=dp[k][j-1]-tot[k]^2
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++)
	{
		dp[1][i] = tot[i] * tot[i];
	}
	for (int i = 2; i <= m; i++)
	{
		hh = 1;
		tt = 0;
		for (int j = 1; j <= n; j++)
		{
			while (hh < tt)
			{
				if ((dp[i - 1][q[hh + 1]] + tot[q[hh + 1]] * tot[q[hh + 1]] - dp[i - 1][q[hh]] - tot[q[hh]] * tot[q[hh]]) <=2 * tot[j] * (tot[q[hh + 1]] - tot[q[hh]]))//斜率单调递增
				{
					hh++;
				}
				else break;
			}
			ll k = q[hh];
			dp[i][j] = dp[i - 1][k] + (tot[j] - tot[k])*(tot[j] - tot[k]);
			while (hh < tt)
			{
				if ((dp[i - 1][q[tt]] + tot[q[tt]] * tot[q[tt]] - dp[i - 1][q[tt - 1]] - tot[q[tt - 1]] * tot[q[tt - 1]])*(tot[j] - tot[q[tt]]) >= (dp[i - 1][j] + tot[j] * tot[j] - dp[i - 1][q[tt]] - tot[q[tt]] * tot[q[tt]])*(tot[q[tt]] - tot[q[tt - 1]]))
				{
					tt--;
				}
				else break;
			}
			q[++tt] = j;
		//	cout << i << " " << j << " " << dp[i][j] << endl;
		}
	}
	cout << m * dp[m][n] - temp;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	solve();
	dream;
}

C++(clang++11) 解法, 执行用时: 152ms, 内存消耗: 22776K, 提交时间: 2021-02-15 09:10:09

#include<iostream>
using namespace std;
int x,m;
int s[3001]={0},s0;
int n[3001][3001]={0};
int a[3001];
int q[3001];
const int inf=999999999;
double sl(int p,int u,int v)
{
	double sd=n[p][u]-n[p][v]+s[u]*s[u]-s[v]*s[v];
	double sr=(s[u]-s[v]);
	return sd/sr;
}
int main()
{
	cin>>x>>m;
	for(int i=1;i<=x;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	s0=s[x]*s[x];
	for(int i=1;i<=x;i++)
	{
		n[1][i]=s[i]*s[i];
	}
	for(int k=2;k<=m;k++)
	{
		int l=1,r=0;
		for(int i=1;i<=x;i++)
		{
			while(l<r&&sl(k-1,q[l],q[l+1])<2*s[i])
			l++;
			n[k][i]=n[k-1][q[l]]+(s[i]-s[q[l]])*(s[i]-s[q[l]]);
			while(l<r&&sl(k-1,q[r-1],q[r])>sl(k-1,q[r],i))
			r--;
			q[++r]=i;
		}
	}
	cout<<-s0+n[m][x]*m<<endl;
}