程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3734 Blocks(矩陣優化+DP)

POJ 3734 Blocks(矩陣優化+DP)

編輯:C++入門知識

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
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int mod = 10007;
const int maxn = 100;
ll T,n,m;
typedef vector vec;
typedef vector mat;
mat mul(mat &a, mat &b) {
    mat c(a.size(), vec(a[0].size()));
    for(int i = 0; i < a.size(); i++) {
        for(int k = 0; k < b.size(); k++) {
            for(int j = 0; j < b[0].size(); j++) {
                c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % mod;
            }
        }
    }
    return c;
}
mat pow(mat a, ll n) {
    mat b(a.size(), vec(a[0].size()));
    for(int i = 0; i < a.size(); i++) {
        b[i][i] = 1;
    }
    while(n > 0) {
        if(n & 1) b = mul(b, a);
        a = mul(a, a);
        n >>= 1;
    }
    return b;
}
int main() {
    scanf("%d",&T);
    mat a(3, vec(3));
    while(T--) {
        scanf("%lld",&n);
        a[0][0] = 2; a[0][1] = 1; a[0][2] = 0;
        a[1][0] = 2; a[1][1] = 2; a[1][2] = 2;
        a[2][0] = 0; a[2][1] = 1; a[2][2] = 2;
        a = pow(a, n);
        printf("%d\n",a[0][0]);
    }
    return 0;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved