e593: 12382 - Grid of Lamps
Tags : Greedy
Accepted rate : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-31 14:59

Content

在大小為 MxN 的矩形地板上,每個地板有一盞燈。燈有些亮、有些暗。
現在給你每行每列至少需要有幾盞燈亮著。
您至少要點亮幾盞燈才能符合條件。
以下是 5x5 矩形地板上燈亮的情況:

1 0 1 1 0
1 1 1 1 1
0 0 0 1 1
0 1 1 1 0
1 0 0 0 0


每行亮燈的盞數為<3、2、3、4、2>。
每列亮燈的盞數為<3、5、2、3、1>。

Input

輸入第一行包含一個整數T (T ≤ 100),代表測資數量。
每組測資有第一行兩個整數M和N (1 ≤ M, N ≤ 1000),分別代表矩形的行數和列數。
接下來的兩行代表地板上需要燈亮的情況。
第一行表示每行至少需要亮幾盞燈(有M個值)。
第二行表示每列至少需要亮幾盞燈(有N個值)。
注意:一開始地板上的燈全是暗的。

Output

對於每組測資,輸出最少需要點亮幾盞燈。

Sample Input
3
2 2
2 0
0 2
1 4
2
1 0 1 1
2 4
3 1
0 2 1 2
Sample Output
3
3
5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
Greedy
出處:
UVA [管理者:
ig99lp33lp33 (원스)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」