第三场E题

题目链接：https://ac.nowcoder.com/acm/contest/5668/E

题意：给一个序列s，在这个序列里面找出两种不同序列的两两匹配，使得所有两两匹配的差的和最小，输出这个和。

关键词：找规律与动态规划。

做题思路：硬规律，害，推断出长度是4与6的划分（推不出来就GG了，还是要多看看多积累），然后再用动态规划。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn=2e6+10;
typedef long long ll;
ll pre1[maxn],pre2[maxn];
ll dp[maxn],a[maxn];
int main(){
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) 
        dp[i]=inf64,cin>>a[i];
        sort(a+1,a+1+n);//排序好划分
        dp[0]=0;
        for(int i=1;i<=n;i+=2) 
        dp[0]+=a[i+1]-a[i];
        for(int i=4;i<=n;i++) 
        pre1[i]=a[i]+a[i-1]-a[i-2]-a[i-3];
        for(int i=6;i<=n;i++) 
        pre2[i]=a[i]+a[i-1]+a[i-3]-a[i-2]-a[i-4]-a[i-5];
        for(int i=4;i<=n;i++)
        {
            if(i>=4) 
            dp[i]=min(dp[i],dp[i-4]+pre1[i]);//四六
            if(i>=6) 
            dp[i]=min(dp[i],dp[i-6]+pre2[i]);
        }
       cout<<dp[n]<<endl;
    }
}