#P10368. [2021年联测]塔

    ID: 9486 传统题 1000ms 256MiB 尝试: 13 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-有限候选集缩减线性 DP消除被支配候选一维前缀和滚动数组

[2021年联测]塔

题目描述

一座塔共有 nn 层,从上往下第 ii 层有 ii 个房间,编号从 11 到 ii。用 (i,j)(i,j) 表示第 ii 层的第 jj 个房间。共有 kk 个不同的房间里有守卫。

可以任意选一个房间施放以下两种法术。

  1. 消灭所选房间里的所有守卫,仅影响这个房间。
  2. 从所选房间 (i,j)(i,j) 起,消灭一个向下延伸至最底层的三角形区域内的所有守卫。对于每一层 h=i,…,nh=i,\ldots,n,受影响的是 (h,j)(h,j) 到 (h,h−i+j)(h,h-i+j) 的全部房间。

一次法术影响 SS 个房间时,代价为 S+2S+2。没有守卫的房间也计入受影响的房间数。求消灭所有守卫的最小总代价。

输入格式

第一行两个整数 n,kn,k。接下来 kk 行,每行两个整数 xi,yix_i,y_i,表示有守卫的房间。

输出格式

输出一行一个整数,表示最小总代价。

样例

7 11
2 2
3 1
4 3
5 1
5 2
5 5
6 4
7 2
7 3
7 4
7 5
26

数据范围

1≤yi≤xi≤n1\le y_i\le x_i\le n,所有守卫房间互不相同,0≤k≤n(n−1)/20\le k\le n(n-1)/2。

子任务 分值 nn 上界 kk 上界 附加限制
1 10
2 25 10310^3 10510^5 依赖 1
3 20 10510^5 100
4 10 10510^5 n,kn,k 和守卫位置均随机生成
5 35 依赖 1–4

原 PDF 题面