UVa 10198 - Counting

( Tip: 點擊左上方的三橫槓選單按鈕，可以收起左側 Pdf 頁。)

Step 1. 題目概要

給定一個數字n，求有多少種由1,2,3,4所構成的串位數之和為n。數字4要視為1。

  • 例如：n=3，則符合規則的共會有13種：
    1. 111 = 1+1+1
    2. 114 = 1+1+1
    3. 141 = 1+1+1
    4. 144 = 1+1+1
    5. 411 = 1+1+1
    6. 414 = 1+1+1
    7. 441 = 1+1+1
    8. 444 = 1+1+1
    9. 12 = 1+2
    10. 42 = 1+2
    11. 21 = 2+1
    12. 24 = 2+1
    13. 3 = 3

Step 2. 解題思路

  • 本題有兩個要點：一是動態規劃，二是大數運算。
    1. 首先先做dp遞迴建表：
      • dp[n]=k 表示寫出數字n的方式有k種
      • 在這些序列中，以1開頭的序列總數為dp[n-1]，以2開頭的序列總數為dp[n-2]，以3開頭的序列總數為dp[n-3]，以4開頭的序列總數為dp[n-4]，而由於4的值必須視為1，故dp[n-4]=dp[n-1]
      • 因此推廣公式後得到：dp[n]=dp[n-1]+dp[n-2]+dp[n-3]+dp[n-1] 開始遞迴
      • 邊界條件：dp[1]=2; dp[2]=5; dp[3]=13
    2. 接下來將處理大數運算：
      • 當數值超過10000時便進行壓縮一次，重複處理直到計算完畢

Step 3. 範例輸入與輸出 - Sample Input and Output

Step 4. 參考程式碼 - Accepted Code

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
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
int main() {
    //dp遞迴建表
    int dp[1005][106]; //dp[n][大數運算用]=k 表示寫出數字n的方式有k種
    memset(dp,0,sizeof(dp)); //初始化為全0
    dp[1][0]=2; dp[2][0]=5; dp[3][0]=13;
    for(int i=4;i<=1000;i++) {
        for(int j=0;j<=105;j++) {
            dp[i][j]=dp[i-1][j]+dp[i-2][j]+dp[i-3][j]+dp[i-1][j];
        }
        //大數運算
        for(int j=0;j<=105;j++) {
            if(dp[i][j]>9999) {
                dp[i][j+1]+=dp[i][j]/10000;
                dp[i][j]%=10000;
            }
        }
    }
    //input
    int n,k;
    while(cin>>n) {
        k = 105;
	while (!dp[n][k] && k) {
            k--;
        }
	cout<<dp[n][k--];
	while (k >= 0) {
	    printf("%04d",dp[n][k --]); //靠左對齊，寬度為4，缺空處補0
        }
	puts(""); 
    }
    return 0;
}