P2301 就是干！题解

· · 题解

观察发现，假设要选四根木棒长度分别为 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;
}