CF797F. Mice and Holes

发表于 | 阅读数

给$n$只老鼠坐标，$m$个洞的坐标和容量，求老鼠入洞最小位移

关键!!,考虑$x_i<x_j$,两个洞$d_i<d_j$

  • 假设洞都在左右两侧，选洞随意。
  • 假设洞都在中间，显然选$x_i\rightarrow d_i$,$x_j\rightarrow d_j$
  • 假设一个洞都在中间，一个洞再另一侧，显然选$x_i\rightarrow d_i$,$x_j\rightarrow d_j$

综上坐标小的选择的洞坐标$\leq$坐标大的选择的洞坐标

两个排序后，就可以设状态$dp[i][j]$，前$i$个洞里放了$j$个老鼠。

$sum(i,k,j)$表示$\sum_{t=k+1}^j abs(x[t]-d[i])$

括号内单调队列优化即可，注意边界即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 5e3 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

pii d[N];
int x[N];
ll dp[N][N];
ll sum[N];
ll s[N];
int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; i++)
        x[i] = read();
    for (int i = 1; i <= m; i++)
    {
        d[i].first = read();
        d[i].second = read();
    }

    sort(1 + x, 1 + x + n);
    sort(1 + d, 1 + d + m);

    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = 1e18;
    dp[0][0] = 0;
    for (int i = 1; i <= m; i++)
    {
        s[i] = s[i - 1] + d[i].second;
        deque<int> q;
        for (int j = 1; j <= n; j++)
            sum[j] = sum[j - 1] + abs(x[j] - d[i].first);
        for (int j = 0; j <= n; j++)
        {

            dp[i][j] = dp[i - 1][j];
            while (!q.empty() && dp[i - 1][q.back()] - sum[q.back()] > dp[i - 1][j] - sum[j])
                q.pop_back();
            q.push_back(j);
            while (!q.empty() && q.front() < j - d[i].second)
                q.pop_front();
            if (!q.empty())
                dp[i][j] = min(dp[i][j], dp[i - 1][q.front()] - sum[q.front()] + sum[j]);
        }
    }

    if (dp[m][n] >= 1e18)
        cout << -1 << endl;
    else
        cout << dp[m][n] << endl;
}