6302: 【回溯】华为2024秋招-俄罗斯方块
金币值：
1
时间限制：4.000 s
内存限制：128 M
正确：19
提交：40
正确率：47.50% 命题人：
题目描述
在俄罗斯方块游戏中，只有
1种大方块，由四个正方形小方块组成。
现在，请计算在给定网格大小的情况下，最多可以放置多少个大方块。
放置规则如下:
- 1、网格为正方形网络
- 2、方块不能重叠。
- 3、方块不能超出网格的边界。
- 4、网格中部分位置不能放置方块。
输入格式
n k
y1 x1
y2 x2
...
表示边长为
n的正方形网格，有k个位置不能放置方块。
接下来
k行坐标对，y表示自上向下的第几行，x表示自左向右的第几列(坐标从0开始编号，左上角为0 0)。
n的范围：[1,8]
k的范围：[0,64]
x、y的范围：[0,n)
输出格式
最多能放下多少大方块。
输入样例 复制
2 0输出样例 复制
1提示
最优策略是选择编号为
3到10、11到12、13到18的业务，总计获得的利润为5。这种选择允许最大化利用可用的基站，同时避免重叠。