2020牛客暑期多校训练营（第三场） E-Two Matchings

题目大意

长度为n的排列是一个数组p = [p1,p2,...,pn] ，其中每个整数为1到n中的一个数，且每个数恰好出现一次。本题对于任意i，。（排列中的数两两对应）
给定一个数组a （0≤a≤10^9，并且n是偶数且大于等于4）。 输出排列的最小和次小成本。（每对数之差的总和）

解题思路

显然最小花费很好求，对元素进行排序，对相邻的两两求差，求和即可。

次小的就比较棘手，我们先举几组样例，从小到大排序，并找出每组的次小匹配方案。将每个被减数标上'+'号，每个减数标'-'号。

可以发现，四个一组的永远是"- - + +"，而六个一组的永远是"- - + - + +"。
每4个元素一组的次小即为a[4]-a[2]+a[3]-a[1]=a[4]+a[3]-a[2]-a[1]，且每6个元素的次小花费即为a[6]-a[1]+a[3]-a[2]+a[5]-a[4]。
！！！由此想到，任何数列都可以拆成4个元素和6个元素一组的组合，而次小方案中以上的方案是固定的！！！

所以就可以使用dp了，dp[i] 表示前i个数的次大值为dp[i]。所以可以得到：
dp[i]=min(dp[i-4]+a[i]+a[i-1]-a[i-2]-a[i-3],dp[i-6]+a[i]+a[i-1]-a[i-2]+a[i-3]-a[i-4]-a[i-5]);

下面直接上代码：

AC代码

#include
#define ll long long
using namespace std;
ll a[200010],dp[200010];
int main()
{
    ll t,n,ans,i;
    scanf("%lld",&t);
    while(t--)
    {
        ans=0;
        scanf("%lld",&n);
        for(i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        for(i=2;i<=n;i+=2)
            ans+=a[i]-a[i-1];
        dp[2]=1ll<<60;
        dp[4]=a[4]+a[3]-a[2]-a[1];
        dp[6]=a[6]+a[5]-a[4]+a[3]-a[2]-a[1];
        for(i=8;i<=n;i+=2)
            dp[i]=min(dp[i-4]+a[i]+a[i-1]-a[i-2]-a[i-3],dp[i-6]+a[i]+a[i-1]-a[i-2]+a[i-3]-a[i-4]-a[i-5]);
        printf("%lld\n",ans+dp[n]);
    }
}