g488 - COVID-101

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算經過 $x$ 天後 COVID-101 病毒的數量 $n(x)$，其中 $n(x) = n(x - 1) + x^2 - x + 1$，且 $n(1) = 1$。

解題思路

題目給定一個遞迴關係式，要求計算特定天數的病毒數量。由於 $x$ 的範圍較小 (<= 200)，可以直接使用動態規劃 (Dynamic Programming) 的方式，從 $n(1)$ 開始，依序計算到 $n(x)$。 程式碼中，nx[i] 儲存第 $i$ 天的病毒數量。迴圈從 $i = 2$ 開始，根據遞迴關係式計算 nx[i]，直到計算到 nx[n]，最後輸出 nx[n]。 也可以觀察到 $x^2 - x + 1$ 可以看作是一個二次函數，但直接使用遞迴關係式計算更為簡潔。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
long long nx[205],n;
int main(){
	cin >> n;
	nx[1]=1;
	for(int i=2;i<=n;++i){
		nx[i]=nx[i-1]+i*i-i+1;
	}
	cout << nx[n];
}