【Newcoder】2020牛客暑期多校训练营（第三场） E - Two Matching | dp、结论

Two Matchings

https://ac.nowcoder.com/acm/contest/5668/E

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

题目大意：
给出一个序列定义一个序列的权值为：图片说明，其中p一个全排列

问第一小和第二小的序列的权值和

其中对p有要求：
图片说明满足并且

并且第一小与第二小的排列任何位置都不相同。

题目思路：

根据图片说明可知：

i在全排列中的位置是pi，pi又在第i个位置

所以这个全排列的性质是每两个元素之间进行了交换

也就说题目所要求的权值转换成为将序列分成N/2组每组的差值的绝对值最小

那么第一小绝对是排序后相邻两元素的差值和(没有一种差值比这小了)

第二小呢？

第二小会考虑到一些问题，题目中指出第一小与第二小的排列任何位置都不相同，那么就是说我们需要在排序之后打乱所有的顺序。也就是说在排序后继续做n/2次交换，使得相邻差值和最小。

此时有个结论：由于4和6可以把偶数都表示出来了，并且权值进行交换的话，写规律可以发现等于8的时候拆成2个4，比拆成1个8好，或者说8的最优情况其实就是2个4，由此可得10的话就是 6 与 4，12就是...

这样就会发现很像背包的dp

所以只需要计算一下6个数交换的最小值与四个数交换的最小值即可。

Code：

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define rep(i,n) for(int i=1;i<=(n);i++)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=2e7+10;
const int maxn =2e5+10;
const int mod=998244353;
const int Mod = 1e9+7;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
    in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
map<ll,int>mp;
ll num[maxn],cop[maxn];
ll dp[maxn];
ll cal(int x,int y){
    return min((cop[y]-cop[y-2]+cop[y-1]-cop[x])*2,(cop[y]-cop[x]+cop[y-1]-cop[y-2])*2);
}
ll cal_1(int x,int y){
    return cop[y]+cop[y-1]-cop[y-2]-cop[y-3];
}https://ac.nowcoder.com/acm/contest/5668#submit/{%22onlyMyStatusFilter%22%3Atrue%2C%22problemIdFilter%22%3A%22209387%22}
ll cal_2(int x,int y){
    ll tempa = cop[y]+cop[y-1]+cop[y-3]-cop[y-2]-cop[y-4]-cop[y-5];
    ll tempb = cop[y]+cop[y-1]+cop[y-2]-cop[y-3]-cop[y-4]-cop[y-5];

    return min(tempa,tempb);
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        read(n);
        for(int i=1;i<=n;i++){
            read(num[i]);
            cop[i] = num[i];
        }
        sort(cop+1,cop+1+n);
        ll ans = 0;
        for(int i=1;i<=n;i+=2)
            ans += 2*abs(cop[i+1]-cop[i]);
        dp[0] = 0 ;
        for(int i=4;i<=n;i+=2){
            dp[i] = INF;
            if(i-4 == 0||i-4>=4)
                dp[i] = min(dp[i],dp[i-4]+cal_1(i-3,i));
            if(i-6 == 0||i-6>=4)
                dp[i] = min(dp[i],dp[i-6]+cal_2(i-5,i));
        }
        printf("%lld\n",ans/2+dp[n]);
    }
    return 0;
}
/**
0 1 1 1 1 1
0 1 0 1 1 1
0 1 0 1 1 1
**/