week8清掃衛生.
連續M個位置上清掃不超過Q個位置情況下得到的最大價值;
我的想法是這樣:
保留前M個位置是否清掃T;
狀態轉移爲:
M個位置若不超過Q-1個選中,那麼選中該位置,++T>>1,;
M個位置若恰有Q-1個選中,那麼找出最小那個與之比較;
有一點很奇怪:
垃圾總不會是負數吧?這樣的話我直接選中然後不斷後移與之前的那個最小值比較,超過它就替換,否則不選;
至於M我可以保留成一個長爲M的二進制序列,因爲這裏M小於10,完全足夠了.
week9:
看了下這題裏大佬的答案 嚇到魂飛 什麼嘛
蛋糕是2*1的,盒子是N*M的,求裝滿的方案數.
N*M%2肯定沒有方案啦 總不能先吃掉一半或者立起來吧
題目限死了m在3-5之間;
事情大概是這樣:
n行m列我們用(i,j)表示;
由於從上往下,所以前面的行肯定已經滿了;
我們只留對下一行的影響,豎放記1,橫放記0;
枚舉記0的位置標好下一行,得出下一行的序列;
所以這其實是個深搜?這是如假包換的dp啊.
完全卡住了...
生無可戀的答案 主要是,答案跟通過的其他代碼,差得有點忒遠啊.
和藹可親的答案 略略進階 然而並不能看懂
更加生無可戀了.
网友评论