黑皮书上的题（最优布车方案），高手指点以下。
阶梯"型棋盘指的是,每一行的格子只出现在一些连续的列上.从第二行开始,每行的起始列数不小于上一行的起始列数,且终止列数也不小于上一行的终止列数.给出一个阶梯棋盘,放上尽量少的"车",控制所有的格子.一个车可以控制和他在同一行和同一列的所有格子.
┍┯┯┓ {从左至右编号1,2,3,4,5,6
┝┿┿┥ {从上至下标号a,b,c,e,f,g
┝┿┿┿┯┓
┕┷┿┿┿┿┑ {棋1(1,a)棋2(2,c])棋3(3,e)棋(6,d)}
┝┿┿┿┥
┕┷┷┿┥
┝┥
┕┛
或如下表示(其中*表示格子,+表示有车的格子)
+**
***
*+***
***+
+***
*
*
详细的讲一下怎么做,最好证明一下为什么用贪心法正确.
谢谢！
[解决办法]
up
[解决办法]
不好意思，题目没看懂
