6706: BZOJ2706:[SDOI2012]棋盘覆盖
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
在一个N*M个方格组成的棋盘内,有K个方格被称为特殊方格。我们要使用一组俄罗斯方块来覆盖这个棋盘,保证特殊方格不能被覆盖,非特殊方格只能被一个俄罗斯方块覆盖,求最多能容纳的俄罗斯方块的数量。 已知有以下三组俄罗斯方块,一个棋盘可能用其中的某一组。
输入格式
第一行三个整数,N,M,K,和一个字符,type,为所用的俄罗斯方块组。
接下来K行每行两个整数,X,Y,表示第X行第Y列为特殊方格。
输出格式
一个整数,为所求的答案。
【样例输入1】
8 8
【样例输出1】
32
【样例输入2】
7 6
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 |
样例输入
样例输出
提示
没有写明提示
题目来源
round1 day1