AYIT夏休み合宿2週目水曜試合Bダンスカーペット

B-ダンスカーペット
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status Practice HDU 2154
Description
長い間運動が不足していたため、黒さんは自分の体が太っていることに気づいて、フィットネスをしたいと思っていました.もっと正確にはダイエットです.黒ちゃんは丸い毛布を買ってきて、それを3等分して、それぞれA、B、Cと表記して、「ダンス毛布」と呼ばれています.彼の運動方法は毎回Aから踊り始め、毎回勝手に他のブロックに飛び込むことができますが、最後にはAに戻らなければなりません.その場で踊ることはできません.ダイエット効果を達成するために、黒さんは毎日n回も踊り続けています.ある日、彼は突然n回踊ったときのいくつかの踊り方を知りたいと思っていましたが、何日も考えていました.今すぐ彼を手伝ってもらって、全部でどれだけの踊り方があるか計算してください. 
 
Input
テスト入力には、いくつかのテスト例が含まれます.各試験例は1行を占め、nの値(1<=n<=1000)を表す.nが0の場合、入力は終了します. 
 
Output
各試験例の出力は1行を占め、ジャンプ法が非常に多いため、10000に対する型取りの結果を出力する.
 
Sample Input

      
      
      
      

       
       
       
       2 3 4 0 
      
      
      
      

 
Sample Output

      
      
      
      

       
       
       
       2 2 6 
      
      
      
      

 
ぶんせき
本題には2つの方法があり、1つ目は法則を探すことであり、この法則はa[i]=(a[i-1]+a[i-2]*2)%10000である.
結果は大きくなる可能性があるので、10000に余裕を取る必要がありますが、実はa[i-1]、a[i-2]はすでに余裕を取っています.

1
2
3
4
5
6
7
8
9
10
11
12

#include<stdio.h>
int main()
{
    int n,i,a[1010];
    a[1]=0;
    a[2]=2;
    for(i=3;i<1005;i++)
        a[i]=(a[i-2]*2+a[i-1])%10000;
    while(scanf("%d",&n)&&n)
        printf("%d
",a[n]);
    return 0;
}

2つ目は大神が書いたもので、深捜と呼ばれていますか?わかったら保存しておこう

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int dp[1010][5];
void init()
{
    dp[2][0]=2;
    dp[2][1]=1;
    dp[2][2]=1;
    for(int i=3; i<=1005; i++)
    {
        dp[i][0]=((dp[i-1][1]%10000)+(dp[i-1][2]%10000))%10000;
        dp[i][1]=((dp[i-1][0]%10000)+(dp[i-1][2]%10000))%10000;
        dp[i][2]=((dp[i-1][0]%10000)+(dp[i-1][1]%10000))%10000;
    }
}
int main()
{
    init();
    int num=0;
    while(cin>>num&&num)
        cout<<dp[num][0]<<endl;
return 0;
}

実はこの運行にかかる時間はもっと長くて、証明は最も良い方法ではありません