AcWing - 1326 军训队列

传送门：AcWing - 1326

思路分析

贪心的想，最小化差值，大小相近的放在一起，所以先对数据进行排序
dp[i][j]表示前面i个人，分为j个队列的最小值
对答案有影响的就是最后一个队列怎么排的
枚举最后一个队列的起始位置，然后就可以转移了

样例输入

3 2
170 180 168

样例输出

4

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;

int a[555];
int dp[555][555];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)cin>>a[i];
    sort(a+1,a+1+n);
    mem(dp,INF);
    dp[0][0]=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i && j<=m; j++)
            for(int k=i; k>=j; k--)
                dp[i][j]=min(dp[i][j],dp[k-1][j-1]+(a[i]-a[k])*(a[i]-a[k]));

    cout<<dp[n][m]<<endl;






    return 0;
}