#P18467. LIS on Grid
LIS on Grid
LIS on Grid
给定一个有 行、 列的网格。行从上到下编号为 ,列从左到右编号为 ,第 行、第 列的格子记为 。
你要将其中一些格子涂黑:对于每一列 ,必须恰好涂黑 个格子。
涂色后,你的代价是黑格的最长严格递增子序列长度。准确地说,它是满足下列条件的最大整数 :存在格子序列 ,使得
- ;
- ;
- 每个 都是黑格。
求你能取得的最小代价,并输出一种达到该代价的涂色方案。
输入格式
第一行包含整数 (),表示测试用例数。随后依次描述每个测试用例。
每个测试用例第一行包含两个整数 (,),分别表示行数和列数。
第二行包含 个整数 (),其中 是第 列必须涂黑的格子数。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,首先输出一行一个整数,表示能够达到的最小代价。
随后输出 行,每行是长度为 、仅由 . 和 # 组成的字符串。第 行字符串的第 个字符为 # 表示格子 涂黑,为 . 表示该格子保持白色。
每列的黑格数必须恰为给定的 。可以输出任意一种最优方案,判题器按实际涂色检查。
原样例输入
4
2 4
1 1 1 1
3 3
3 3 3
4 4
4 3 2 1
4 5
2 3 4 3 2
原样例输出
1
....
####
3
###
###
###
2
###.
#...
####
##..
2
..###
.####
####.
###..
帮助理解
同一行的两个黑格不能同时出现在上述严格递增子序列中,同一列也不能。第一个样例将所有黑格放在同一行,代价为 。第二个样例所有格子都必须为黑色,代价为 。上面的输出完整保留原题提供的四个用例及其方案;其他最优方案同样合法。