题目链接: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; } }