2706. [SDOI2012]棋盘覆盖
#2706. [SDOI2012]棋盘覆盖
题目描述
在一个N*M个方格组成的棋盘内，有K个方格被称为特殊方格。我们要使用一组俄罗斯方块来覆盖这个棋盘，保证特殊方格不能被覆盖，非特殊方格只能被一个俄罗斯方块覆盖，求最多能容纳的俄罗斯方块的数量。
已知有以下三组俄罗斯方块，一个棋盘可能用其中的某一组。
输入格式
第一行三个整数，N,M,K，和一个字符，type，为所用的俄罗斯方块组。
接下来K行每行两个整数，X,Y，表示第X行第Y列为特殊方格。
输出格式
一个整数，为所求的答案。
【样例输入1】
8 8 0 A
【样例输出1】
32
【样例输入2】
7 6 6 C
3 1
3 6
5 3
5 4
5 7
6 7
【样例输出2】
12
【数据范围】
测试点
|
N,M
|
K
|
type
---|---|---|---
[1, 6]
|
0 < N,M <= 100
|
0<=K<=N*M
|
A
[7, 12]
|
N=M=2^L,0<L<=200000
|
K=1
|
B
[13, 20]
|
0<N,M<=11
|
0<=K<=N*M
|
C