A12642 | Zoning Restrictions Again
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are planning to build housing on a street. There are $n$ spots available on the street on which you can build a house. The spots are labeled from $1$ to $n$ from left to right. In each spot, you can build a house with an integer height between $0$ and $h$ .
In each spot, if a house has height $a$ , you will gain $a^2$ dollars from it.
The city has $m$ zoning restrictions. The $i$ -th restriction says that the tallest house from spots $l_i$ to $r_i$ (inclusive) must be at most $x_i$ .
You would like to build houses to maximize your profit. Determine the maximum profit possible.
In each spot, if a house has height $a$ , you will gain $a^2$ dollars from it.
The city has $m$ zoning restrictions. The $i$ -th restriction says that the tallest house from spots $l_i$ to $r_i$ (inclusive) must be at most $x_i$ .
You would like to build houses to maximize your profit. Determine the maximum profit possible.
输入格式
The first line contains three integers $n$ , $h$ , and $m$ ( $1 \leq n,h,m \leq 50$ ) — the number of spots, the maximum height, and the number of restrictions.
Each of the next $m$ lines contains three integers $l_i$ , $r_i$ , and $x_i$ ( $1 \leq l_i \leq r_i \leq n$ , $0 \leq x_i \leq h$ ) — left and right limits (inclusive) of the $i$ -th restriction and the maximum possible height in that range.
Each of the next $m$ lines contains three integers $l_i$ , $r_i$ , and $x_i$ ( $1 \leq l_i \leq r_i \leq n$ , $0 \leq x_i \leq h$ ) — left and right limits (inclusive) of the $i$ -th restriction and the maximum possible height in that range.
输出格式
Print a single integer, the maximum profit you can make.
输入输出样例
输入 #1
3 3 3 1 1 1 2 2 3 3 3 2
输出 #1
14
输入 #2
4 10 2 2 3 8 3 4 7
输出 #2
262
In the first example, there are $3$ houses, the maximum height of a house is $3$ , and there are $3$ restrictions. The first restriction says the tallest house between $1$ and $1$ must be at most $1$ . The second restriction says the tallest house between $2$ and $2$ must be at most $3$ . The third restriction says the tallest house between $3$ and $3$ must be at most $2$ .
In this case, it is optimal to build houses with heights $[1, 3, 2]$ . This fits within all the restrictions. The total profit in this case is $1^2 + 3^2 + 2^2 = 14$ .
In the second example, there are $4$ houses, the maximum height of a house is $10$ , and there are $2$ restrictions. The first restriction says the tallest house from $2$ to $3$ must be at most $8$ . The second restriction says the tallest house from $3$ to $4$ must be at most $7$ .
In this case, it's optimal to build houses with heights $[10, 8, 7, 7]$ . We get a profit of $10^2+8^2+7^2+7^2 = 262$ . Note that there are two restrictions on house $3$ and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house $1$ , we must still limit its height to be at most $10$ ( $h=10$ ).
In this case, it is optimal to build houses with heights $[1, 3, 2]$ . This fits within all the restrictions. The total profit in this case is $1^2 + 3^2 + 2^2 = 14$ .
In the second example, there are $4$ houses, the maximum height of a house is $10$ , and there are $2$ restrictions. The first restriction says the tallest house from $2$ to $3$ must be at most $8$ . The second restriction says the tallest house from $3$ to $4$ must be at most $7$ .
In this case, it's optimal to build houses with heights $[10, 8, 7, 7]$ . We get a profit of $10^2+8^2+7^2+7^2 = 262$ . Note that there are two restrictions on house $3$ and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house $1$ , we must still limit its height to be at most $10$ ( $h=10$ ).
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted