CF797F Mice and Holes 题解

首先根据贪心的思想可知，如果老鼠

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)

。

CPP

#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;
}

CF797F Mice and Holes 题解

文章操作

相关推荐

评论

CF797F Mice and Holes 题解