自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 21:36:07，当前版本为作者最后更新于2021-08-29 22:07:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

观察发现，假设要选四根木棒长度分别为 $l_1\leq l_2\leq l_3\leq l_4$。

显然把 $l_1,l_2$ 分一起，$l_3,l_4$ 分一起比其他方法优。

于是，我们把木棍长度从小到大排。

假设 $f_{i,j}$ 表示前 $i$ 条木棒中，分给了 $j$ 人最小矛盾指数，可以得到：

$$f_{i,j}=\min(f_{i-1,j},f_{i-2,j-1}+(a_i-a_{i-1})^2) $$

时间复杂度 $\mathcal{O}(nm)$。

参考代码

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN=505;
int n,m;
ll a[4*MAXN];
ll f[4*MAXN][MAXN];
int main(){
	for(int i=1;i<MAXN;i++)
		f[0][i]=f[1][i]=8e18;
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		cin>>a[i];
	sort(a+1,a+m+1);
	for(int i=2;i<=m;i++){
		for(int j=1;j<=n;j++)
			f[i][j]=min(f[i-1][j],f[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
		f[i][0]=0;
	}
	cout<<f[m][n];
	return 0;
}