[问题] ZJ-b693 棕梠画画

楼主: fatcat8127 (胖胖猫)   2019-05-20 02:24:53
如题( 题目连结:https://zerojudge.tw/ShowProblem?problemid=b693 )
题目的叙述就像是 ZJ664-UVa11725,相邻的格子不能涂上相同的颜色
问 NxN 的棋盘上问符合规定的方法(取模)。
但不同的地方在于每个格子可以选择的颜色只有两种(题目会给颜色编号)且 N 最大是16
我根据UVa11725的解法刻了一个版本( https://ideone.com/xDcn28 )
题目需要状态压缩+动态规划处理Row和Row状态转移时合法方法数的累加。
不过只能通过70%(30% TLE),想问一下题目的不同于UVa11725的特性该怎么用在这题上?
作者: oToToT (屁孩)   2019-05-22 00:37:00
https://pastebin.com/Kdxqk0eM 贴个O(n^2 2^n)的bottom-up DP作法,我个人在这种题目上不太喜欢一层一层转移,一格一格转移有时候会比较好写,不过当然也有题目一定要一层一层转就是了通常我也不太会top-down,因为递回的耗时通常比纯循环高了一些
楼主: fatcat8127 (胖胖猫)   2019-05-26 09:49:00
感谢oT大大 想弱弱的问一下adde和sets的这种写法是什么? 第一次在C++看到,好像JS的函数当作物件的写法
作者: FRAXIS (喔喔)   2019-05-26 10:45:00
C++ Lambda?

Links booklink

Contact Us: admin [ a t ] ucptt.com