Codeforces 385 D Bear and Floodlight
題目鏈接~~>
做題感悟:比賽的時候最後有點蛋疼了,處理點的坐標處理暈了,so~比賽完清醒了一下就AC了。
解題思路:
狀態壓縮DP ,只有 20 個點,如果安排燈的時候只有順序不同的問題,完全可以用狀態壓縮去遞推出來,只是處理點的坐標的時候很麻煩,理清思路就好了。
狀態方程: dp [ S | (1 << i ) ] = max( dp[ S |( 1 << i ) ] , dp[ S ] + W ) , 在狀態 S 的情況下再添加 i 點(S 中先前不含 i 點),這樣一直更新就 ok 了。
代碼(有點挫了):
#include
#include
#include