题面分析

$N$ 有 $1.5 \times 10^7$，而限制只有 $3000$，显然需要离散化一下，离散化完就变成一个 $2 \times 3000$ 的矩形。

然后状态设计和转移比较显然。设 $f_{i,j,0/1/2/3}$ 为当前方案数，表示走到第 $i$ 列，用了 $j$ 个矩形来覆盖，目前一列的覆盖情况是：只有上面、只有下面、上下都有且为同一矩形、上下都有且为不同矩形。手玩一下可以得出转移。

注意转移中不符合本行覆盖限制的情况要删掉。

::::success[Code]

#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>

int rd()
{
    int x = 0,w = 1;
    char ch = 0;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

const int N = 1.5e7 + 5;
const int M = 1e3 + 3;
const int inf = 2e9;

int m,k,n;
int lsh[M],cnt,f[M][M][4];
int a[M][3];
pii q[M];

signed main()
{
    m = rd(),k = rd(),n = rd();
    for(int i = 1;i <= m;i++) q[i] = {rd(),rd()},swap(q[i].fi,q[i].se),lsh[++cnt] = q[i].fi;
    sort(q + 1,q + m + 1);
    sort(lsh + 1,lsh + cnt + 1);
    cnt = unique(lsh + 1,lsh + cnt + 1) - lsh - 1;
    for(int i = 1;i <= m;i++)
    {
        q[i].fi = lower_bound(lsh + 1,lsh + cnt + 1,q[i].fi) - lsh;
        a[q[i].fi][q[i].se] = 1;
    }
    for(int i = 0;i <= cnt;i++) for(int j = 0;j <= k;j++) f[i][j][0] = f[i][j][1] = f[i][j][2] = f[i][j][3] = inf;
    f[0][0][0] = f[0][0][1] = f[0][0][2] = f[0][0][3] = 0;
    for(int i = 1;i <= cnt;i++)
    {
        for(int j = 1;j <= k;j++)
        {
            int tmp = min({f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j-1][3]}),len = lsh[i] - lsh[i-1];
            f[i][j][0] = min({tmp + 1,f[i-1][j][0] + len,f[i-1][j][3] + len});
            f[i][j][1] = min({tmp + 1,f[i-1][j][1] + len,f[i-1][j][3] + len});
            f[i][j][2] = min({tmp + 2,f[i-1][j][2] + len * 2,f[i-1][j][3] + len * 2});
            if(j > 1) f[i][j][3] = min({f[i-1][j-1][0] + len + 1,f[i-1][j-1][1] + len + 1,f[i-1][j][3] + 2 * len,
                                    f[i-1][j-2][0] + 2,f[i-1][j-2][1] + 2,f[i-1][j-2][2] + 2,f[i-1][j-2][3] + 2});
            if(a[i][1] == 1) f[i][j][1] = inf;
            if(a[i][2] == 1) f[i][j][0] = inf;
        }
    }
    cout << min({f[cnt][k][0],f[cnt][k][1],f[cnt][k][2],f[cnt][k][3]});
    return 0;
}