【題解】ZeroJudge d887: 1.山脈種類(chain)

題目敘述:https://zerojudge.tw/ShowProblem?problemid=d887
解題想法:DP

  • 先觀察山脈的步數與高度走勢,假設山脈最高高度 i (1 <= i <= j),總步數 2j (1 <= j <= N)。
  • dp[i][j] 有下圖的狀態轉移關係。直接使用二維陣列編寫程式碼(1)
  • 或,觀察下表的關係,改用一位陣列編寫,如程式碼(2)
j=12345
i=111111
2121+2=31+3=41+4=5
3122+3=54+5=95+9=14
41259+5=1414+14=28
51251428+14=42

程式碼(1)

#include <iostream>
#include <cstring>
using namespace std;

const int maxn=30;
//dp[i][j]:最大高度為i,總步數為2j的組合數
long long dp[maxn][maxn];

int main() {
    int N;
    while (cin >> N) {
        memset(dp, 0, sizeof(dp));
        for (int j=1; j<=N; j++) {
            // 最大高度為1的組合數
            dp[1][j] = 1;
        }
        for (int i=2; i<=N; i++) {
            // 最大高度i, 2 <= i <= N
            for (int j=1; j<i; j++) {
                //總步數2j, j<i
                dp[i][j] = dp[i-1][j];
            }
            for (int j=i; j<=N; j++) {
                //總步數2j, i <= j <= N
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        cout << dp[N][N] << "\n";
    }
    return 0;
}

程式碼(2)

#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n){
        long long a[n+1];
        for (int i = 0; i <= n; i++){
            a[i] = i;
        }
        if (n >= 3){
            for (int i = 3; i <= n; i++){
                for (int j = i; j <= n; j++){
                    a[j] += a[j-1];
                }
            }
        }
        cout << a[n] << "\n";
    }
}

Python code (credit: Amy Chou)

while True:
    try:
        n = int(input())
        a = [i for i in range(n+1)]
        
        if n >= 3:
            for i in range(3, n+1):
                for j in range(i, n+1):
                    a[j] += a[j-1]
        
        print(a[n])
    except:
        break
分享本文 Share with friends