2680:Computer Transformation

keyword

動的計画法　Java

概要

まず1という文字列がある。1ステップ毎に、1は01に、0は10に変換される。n(<1000)ステップ後に00がいくつ現れるかを求める問題。
00, 01, 10, 11のペアがいくつあるかを各ステップ毎に覚えておけば良い。このとき、重複が無いようにするのと、一番右側は常に01であることに注意する。それと当然longなんかでは収まらないので多倍長整数を使うこと。

import java.util.*;
import java.math.*;

class Main{
    public static void main(String args[]){
        BigInteger n00[] = new BigInteger[1001],
                   n01[] = new BigInteger[1001],
                   n10[] = new BigInteger[1001],
                   n11[] = new BigInteger[1001];
        for(int i=1; i<=1000; i++)
            n00[i] = n01[i] = n10[i] = n11[i] = BigInteger.ZERO;

        n01[1] = BigInteger.ONE;
        for(int i=2; i<=1000; i++){
            n10[i] = n10[i].add(n00[i-1]);
            n01[i] = n01[i].add(n00[i-1]);
            n10[i] = n10[i].add(n01[i-1]);
            n00[i] = n00[i].add(n01[i-1]);
            n01[i] = n01[i].add(n10[i-1]);
            n11[i] = n11[i].add(n10[i-1]);
            n01[i] = n01[i].add(n11[i-1]);
            n10[i] = n10[i].add(n11[i-1]);
            n01[i] = n01[i].add(BigInteger.ONE);
        }
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            System.out.println(n00[n]);
        }
    }
}