POJ 3734 Blocks(矩陣優化+DP)
題意:個n個方塊塗色, 只能塗紅黃藍綠四種顏色,求最終紅色和綠色都為偶數的方案數。
該題我們可以想到一個遞推式 。 設a[i]表示到第i個方塊為止紅綠是偶數的方案數, b[i]為紅綠恰有一個是偶數的方案數, c[i]表示紅綠都是奇數的方案數。
那麼有如下遞推可能:
遞推a[i+1]:1.到第i個為止都是偶數,且第i+1個染成藍或黃;2.到第i個為止紅綠恰有一個是奇數,並且第i+1個方塊染成了奇數對應的顏色。
遞推b[i+1]:1.到第i個為止都是偶數,且第i+1個染成紅或綠;2.到第i個為止紅綠恰有一個是奇數,並且第i+1個方塊染成了藍或黃;3.到第i個方塊為止紅火綠都是奇數,並且第i+1個染成紅火綠。
遞推c[i+1]:1.到第i個為止紅綠恰有一個是奇數, 並且第i+1個方塊染成偶數對應的顏色;2.到第i個為止紅綠都是奇數,並且第i+1個方塊染成藍或黃。
即a[i+1] = 2*a[i] + b[i];
b[i+1] = 2*a[i] + 2*b[i] + 2*c[i];
c[i+1] = b[i] + 2*c[i];
因為DP的過程中,每一步都是在重復上一個過程, 所以可以用矩陣相乘來優化算法。
將上述遞推式寫成矩陣相乘的形式:
{ a[i] } {2 1 0}^i{a[0] }
{ b[i] } = {2 2 2} {b[0] }
{ c[i] } {0 1 2} {c[0] }
然後用矩陣快速冪就可以了。
細節參見代碼:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include