RT，学了四边形不等式，有点蒙，但还是做了这道题。

#include<bits/stdc++.h>
using namespace std;
inline bool id(const char ch) {
	return ch>='0'&&ch<='9';
}
inline int read(void) {
	int s=0;
	char ch=getchar();
	while(!id(ch)) ch=getchar();
	while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
const int MAXN=3000+10,MAXM=300+10;
int n,p,w[MAXN],qzh[MAXN],k[MAXN][MAXM],dis[MAXN][MAXN],dp[MAXN][MAXN];
int main() {
	n=read(),p=read();
	for(int i=1;i<=n;i++) w[i]=read(),qzh[i]=qzh[i-1]+w[i];
	for(int i=1;i<=n;i++) for(int j=i,mid;j<=n;j++) mid=(i+j)>>1,dis[i][j]=w[mid]*(mid-i+1)-(qzh[mid]-qzh[i-1])+qzh[j]-qzh[mid]-w[mid]*(j-mid);
	for(int i=0;i<=n;i++) k[i][i]=i,dp[1][i]=dis[1][i];
	for(int l=1;l<=n-p;l++)
		for(int i=1;i<=n-l;i++) {
			int j=i+l;
			dp[i][j]=INT_MAX;
			for(int kk=k[i][j-1];kk<=k[i+1][j];kk++) {
				int anss=dp[i-1][kk-1]+dis[kk][j];
				if(anss<dp[i][j]) dp[i][j]=anss,k[i][j]=kk;
			}
		}
	printf("%d",dp[p][n]);
	return 0;
}

求debug