2020牛客多校 3E.Two Matchings（dp）

题意：

解法：

对a(i)从小到大排序
一组肯定是(1,2)，(2,3)，(3,4)这种两两匹配的，这样最小，
另外一组肯定大一点，分组只有4个一组或者6个一组两种情况，要么是{(1,4),(2,3)}，要么是{(1,3),(2,5),(3,6)}。

一开始我以为只有一次6个一组的，枚举了一下6个一组的位置，然后wa裂了，
如果不确定有多少个6个一组的，就得用dp做了。

ps：
也可以第一组不最贪，换成每组贪一半，这样可以做到两组的权值一样大，
改一下dp的转移方程，一次dp之后乘2就是答案

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e6+5;
int d[maxm];
int a[maxm];
int n;
signed main(){
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        int ans=0;
        for(int i=2;i<=n;i+=2){
            ans+=a[i]-a[i-1];
        }
        for(int i=1;i<=n;i++){
            d[i]=1e18;
        }
        d[4]=a[4]-a[1]+a[3]-a[2];
        for(int i=6;i<=n;i+=2){
            d[i]=min(d[i],d[i-4]+a[i]-a[i-3]+a[i-1]-a[i-2]);
            d[i]=min(d[i],d[i-6]+a[i]-a[i-2]+a[i-3]-a[i-5]+a[i-1]-a[i-4]);
        }
        cout<<ans+d[n]<<endl;
    }
    return 0;
}

---

本文地址：https://blog.csdn.net/weixin_44178736/article/details/107432308