#P10368. [2021年联测]塔
[2021年联测]塔
题目描述
一座塔共有 层,从上往下第 层有 个房间,编号从 到 。用 表示第 层的第 个房间。共有 个不同的房间里有守卫。
可以任意选一个房间施放以下两种法术。
- 消灭所选房间里的所有守卫,仅影响这个房间。
- 从所选房间 起,消灭一个向下延伸至最底层的三角形区域内的所有守卫。对于每一层 ,受影响的是 到 的全部房间。
一次法术影响 个房间时,代价为 。没有守卫的房间也计入受影响的房间数。求消灭所有守卫的最小总代价。
输入格式
第一行两个整数 。接下来 行,每行两个整数 ,表示有守卫的房间。
输出格式
输出一行一个整数,表示最小总代价。
样例
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 | 10 | |||
| 2 | 25 | 依赖 1 | ||
| 3 | 20 | 100 | ||
| 4 | 10 | 和守卫位置均随机生成 | ||
| 5 | 35 | 依赖 1–4 | ||