CF797F Mice and Holes 题解

_Jocularly_ · 2025-11-25 11:03:50 · 题解

首先根据贪心的思想可知，如果老鼠 i 在老鼠 j 的左边，那么对应钻进的洞 p_i 也应该在 p_j 的左边。因为如果出现了老鼠与洞连线彼此交叉的情况，则可以调整为不交叉的选择方式，显然不劣于原情况。所以如果老鼠按照位置排序，它们钻进的洞也应该是按照位置排序的，那么可以根据这个性质动态规划。

设 dp_{i,j} 表示前 i 个洞里有前 j 只老鼠的最小代价，如果枚举前 k 个老鼠在前 i - 1 个洞里，那么有转移方程 dp_{i,j} = \min(dp_{i,j},dp_{i - 1,k} + \sum_{a=k+1}^j {dis_{p_i,a}})，其中 dis_{p_i,a} 表示 p_i 号洞与第 a 号老鼠之间的距离，可以用前缀和来优化求和到 O(1)。优化后总时间复杂度量级为 O(n^3)，默认 n 与 m 同阶，显然会超时。

考虑如何优化。设 s_{i,j} 表示到第 i 个洞的前 j 个老鼠的距离和，那么上述转移方程转化为 dp_{i,j} = \min(dp_{i,j},dp_{i - 1,k} + s_{i,j} - s_{i,k})，显然 s_{i,j} 与 k 无关，因此可以提出，那么转移方程变形为 dp_{i,j} = \min(dp_{i,j},dp_{i - 1,k} - s_{i,k}) + s_{i,j}，括号内的可以通过单调队列来实现，可以做到均摊 O(1) 查询。单调队列优化后的总时间复杂度量级为 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int x[5005];
pair<int,int> p[5005];
int cnt[5005],sum[5005];
int dp[5005][5005];
int q[5005];
signed main(){
    memset(dp,0x3f,sizeof(dp));
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> x[i];
    }
    for(int i=1;i<=m;i++){
        cin >> p[i].first >> p[i].second;
    }
    sort(x + 1,x + n + 1);
    sort(p + 1,p + m + 1);
    for(int i=1;i<=m;i++){
        sum[i] = sum[i - 1] + p[i].second;
    }
    if(sum[m] < n){
        cout << -1;
        return 0;
    }
    for(int i=0;i<=m;i++){
        dp[i][0] = 0;
    }
    for(int i=1;i<=m;i++){
        int l = 0,r = 0;
        q[++ r] = 0;
        for(int j=1;j<=min(sum[i],n);j++){
            cnt[j] = cnt[j - 1] + abs(p[i].first - x[j]);
            dp[i][j] = dp[i - 1][j];
            while(l <= r && j - q[l] > p[i].second) l ++;
            while(l <= r && dp[i - 1][q[l]] - cnt[q[l]] > dp[i - 1][j] - cnt[j]) l ++;
            q[++ r] = j;
            if(l <= r) dp[i][j] = min(dp[i][j],dp[i - 1][q[l]] - cnt[q[l]] + cnt[j]);
        }
    }
    cout << dp[m][n];
    return 0;
}