RGB塗装問題

説明:

1列に並ぶn個の格子があり、赤(Red)、ピンク(Pink)、緑(Green)の3色で各格子を塗り、各格子に1色塗り、隣接する格子が同色でないことを要求し、しかも首尾両格子も異なる色である.すべての要求を満たす塗り方を求める.以上が有名なRPGの難題である.
Input入力データには複数のテストインスタンスが含まれており、各テストインスタンスが1行を占め、1つの整数Nで構成されている(0 Outputは各テストインスタンスについて、すべての要求を満たす塗布法を出力し、各インスタンスの出力が1行を占めている.Sample Input 1 2 Sample Output 3 6分析:どのようなプッシュ問題がいつもそんなにうまくいかないのか分からないし、しかもこの問題はそんなに簡単だ.考え方は簡単で、n+1 n+1 n+1の場合とn n n nおよびn−1 n−1 n−1の関係は2つの場合に分けられる.

n番目のn n個の色は、1個目と同じである(この場合、n n n n n n nの配列ではありえないので、n−1 n−1 n−1 n−1の配列に関係する)、f 1(n+1)=2

第n n n個の色が第1個と異なる場合、f 2(n+1)=f(n)となる.f2(n+1)=f(n). f2(n+1)=f(n). 従って、f(n+1)=f(n)+2∗f(n−1)f(n+1)=f(n)+2*f(n−1)=f(n)+2∗f(n−1)

初期条件f(1)=3,f(2)=f(3)=6 f(1)=3,f(2)=f(3)=6 f(1)=3,f(2)=f(3)=6
長さnの列を考慮して、iビットの文字をs[i]s[i]s[i]s[i]で表す.

前n−1 n−1 n−1ビットからなるシリアルが合法であれば、首尾が異なるため、もう1ビットを追加する場合、1 1 1つの方法しかない.すなわち、s[n]=s[n−1]s[n]=s[n−1]s[n]=s[n−1]

前n−1 n−1 n−1位からなる列が合法でない場合、後合法、すなわち首尾が同じであることによる不合法が追加されると、前n−2 n−2 n−2位からなる列は必ず合法である.このときn n番目のnビットには2,2種類の追加方法がある.すなわちs[n]=2∗s[n−2]s[n]=2*s[n]=2∗s[n−2]

総じて:s[n]=s[n−1]+2∗s[n−2]s[n]=s[n−1]+2*s[n−2]s[n]=s[n−1]+2∗s[n−2]

境界条件:f(1)=3;f ( 2 ) = 6 ; f ( 3 ) = 6 . f(1)=3;f(2)=6;f(3)=6. f(1)=3;f(2)=6;f(3)=6.

コード参照:

#include
int main()
{
	int n;
	while (scanf("%d",&n)!=EOF){
		long long z[51]={0,3,6,6};// n=50 ， 16 ， int， long long
		for (int i=4;i<=n;i++)
		{
			z[i]=z[i-1]+z[i-2]*2;
		}
		printf("%lld
",z[n]);
	}
}