【題目敘述】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";
}
}