2020牛客暑期多校训练营（第三场）E、Two Matchings（思维、dp）

题面：

题意：

定义一个排列为 $p$ 匹配，当且仅当 $p_{i}! = i <mtext> </mtext> a n d <mtext> </mtext> p_{p_{i}} = i$ ，我们可以发现p匹配中两两配对。

定义两个匹配 $p, q$ 不相同，对于所有的 $i \in [1, n], p_{i} \neq q_{i}$

给定一个数组a，定义一个p匹配的花费为 $(\sum_{i = 1}^{n} a b s (a_{i} - a_{p_{i}})) / 2$

给定序列a，找两个不同的匹配，使得他们的花费和最小。

题解：
我们设 n=2*k
那么该题意转化为：给 2k 个点的完全图，每个点有个数值，每条边的权重是相连两个数值的差的绝对值，请找出两个边没有交集的完全匹配使得这两个完全匹配的所有边的权重和最小（我们把每条边的权重是相连两个数值的差的绝对值即可，因为最终答案要除以2）。

（1）此题等价于找一些长度为偶数的环使得这些环恰通过每个点一次，且所有边的总权重最少。

（2） 2x 个点所构成的环的权重和的最小值为 2 *（这2x个点中最大值-这2x个点中最小值）。我们dp处理的时候，把这个系数2放到了最后。

（3）先把所有点按照权重排序，最佳解一定是出现在每个环都是由排序后连续的点构成。

（4）若某个环长度 ≥ 8，总是可以拆成一些长度为 4 或 6 的环且总边权更小。

（5）于是我们就可以把点的权重排序后，对于前 2x 个点当作子题来动态规划啦，转移时只要枚举最后一个点所在的环长度是 4 还是 6 即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxp=1100;
const int maxm=100100;
const int up=100000;

ll a[maxn],dp[maxn];

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        dp[2]=inf;
        dp[4]=a[4]-a[1];
        dp[6]=a[6]-a[1];
        for(int i=8;i<=n;i+=2)
            dp[i]=min(dp[i-4]+a[i]-a[i-3],dp[i-6]+a[i]-a[i-5]);
        printf("%lld\n",dp[n]*2);
    }
    return 0;
}