题解归档 - cf104114E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104114E
• 本地来源：problems/cf104114E/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/E
• 原始标题：cf104114E - Exercise

思路

cf104114E - Exercise

Sort all 2n students by skill. A minimum absolute-difference perfect matching on a line has an optimal non-crossing form.

With only one forbidden edge per original pair, there is an optimal non-crossing matching where every matched edge spans at most 5 sorted positions. If an outer edge spans >= 7, the first six involved positions can be rematched internally (each colour appears at most twice, so an allowed perfect matching exists) without increasing the line metric cost, and the outer edge can be removed. Repeating gives span <= 5.

Therefore the sorted sequence can be tiled by independent blocks of size 2, 4, or 6. For each block, try all Catalan non-crossing matchings inside the block and forbid matching equal original pair ids.

dp[i] = min cost for the first i sorted students, with transitions from the last block size 2/4/6.

Complexity: O(n) after sorting.

代码

来源：problems/cf104114E/solution.cpp

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

vector<vector<pair<int,int>>> mats[7];

vector<vector<pair<int,int>>> gen(int l,int r){
    if(l>r) return {{}};
    vector<vector<pair<int,int>>> out;
    for(int j=l+1;j<=r;j+=2){
        auto A=gen(l+1,j-1);
        auto B=gen(j+1,r);
        for(auto a:A){
            for(auto b:B){
                vector<pair<int,int>> cur={{l,j}};
                cur.insert(cur.end(),a.begin(),a.end());
                cur.insert(cur.end(),b.begin(),b.end());
                out.push_back(cur);
            }
        }
    }
    return out;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for(int k:{2,4,6}) mats[k]=gen(0,k-1);

    int n;
    cin>>n;
    int N=2*n;
    vector<pair<ll,int>> a(N);
    for(int i=0;i<N;i++){
        cin>>a[i].first;
        a[i].second=i/2;
    }
    sort(a.begin(),a.end());

    const ll INF=(1LL<<62);
    vector<ll> dp(N+1,INF);
    dp[0]=0;
    for(int i=2;i<=N;i+=2){
        for(int k:{2,4,6}){
            if(i<k||dp[i-k]>=INF) continue;
            for(auto &mat:mats[k]){
                bool ok=true;
                ll cost=0;
                for(auto [u,v]:mat){
                    int U=i-k+u,V=i-k+v;
                    if(a[U].second==a[V].second){
                        ok=false;
                        break;
                    }
                    cost+=a[V].first-a[U].first;
                }
                if(ok) dp[i]=min(dp[i],dp[i-k]+cost);
            }
        }
    }

    cout<<dp[N]<<"\n";
    return 0;
}