資訊之芽 動態規劃 Ex2. 塗色問題 4 種顏色的狀況

RGBY
Y:Yellow
Blue 後面不能是 Yellow
其餘條件同！

Array and init

#include <iostream> using namespace std; int globalArray[3]; int main(int argc, const char * argv[]) { int localArray[3]; int localArrayWithInit[3]={1}; for (int i=0;i<3;i++) cout << globalArray[i]; //000 cout << endl; for (int i=0;i<3;i++) cout << localArray[i]; //random cout << endl; for (int i=0;i<3;i++) cout << localArrayWithInit[i]; //100 return 0; }

資訊之芽 動態規劃

資訊之芽 動態規劃 Ex2. 塗色問題

#include <iostream>
using namespace std;
unsigned long long int F[1000001][3];
unsigned long long int f1(unsigned long long int m){
    F[1][0]=1;
    F[1][1]=1;
    F[1][2]=1;
    
    for (unsigned long long int n=2;n<=m;n++){
        F[n][0] =F[n-1][0]+F[n-1][1]+F[n-1][2];
        F[n][1] =F[n-1][1]+F[n-1][2];
        F[n][2] =F[n-1][0]+F[n-1][2];
        //cout << F[n][0]+ F[n][1]+ F[n][2] << ",";
        
    }
    return  F[m][0]+ F[m][1]+ F[m][2];
}
//https://oeis.org/A095263
unsigned long long int G[1000001];
unsigned long long int f2(unsigned long long int m){
    G[1]=3;
    G[2]=7;
    G[3]=16;
    
    for (unsigned long long int n=4;n<=m;n++){
        G[n]=3*G[n-1]-2*G[n-2]+G[n-3];
    }
    return G[m];
    
}

int main(int argc, const char * argv[])
{
    unsigned long long int m;
    cin >> m;
    cout << f1(m) << endl;
    cout << f2(m) << endl;
    return 0;
}