【題解】ZeroJudge d261: 11000 – Bee

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

  • 除了第一隻「神奇」的母蜂永遠都不會死,其餘的母蜂和公蜂,會在每一年生育後死去。
    • 初始值:F[0] = 1 (神奇的母蜂), M[0] = 0 (公蜂)
    • 狀態轉移:F[i] = M[i-1] + 1, M[i] = F[i-1] + M[i-1]
#include <iostream>
using namespace std;

int main() {
    int N;
    while (cin >> N){
        if (N == -1) break;
        long long F = 1, M = 0;
        for (int i = 1; i <= N; i++){
            long long tmp = M;
            M += F;
            F = tmp + 1;
        }
        cout << M << " " << M + F << "\n";
    }
}
分享本文 Share with friends