zerol : 棋盘上的車
3 年,11 月前
题目
http://acm.ecnu.edu.cn/problem/3438/
题意
给定一个由 n 条高度不等的列组成的棋盘,其中所有列的底边位于同一水平线上。求放置 k 个互不攻击的車的方案总数。(車能互相攻击当且仅当能通过棋盘上连续的一行或一列格子直接连在一起)
题解
观察到从最下面一行开始往上,行断开后不可能重新接在一起,所以从断开处横向切开 很可能 可以分解为两个子问题。当然也可以把它看做是一棵树,树上的每一个结点有高和宽,只有有公共边的情形下两个结点才会相连。
...查看全文