d289 - 多元一次方程式

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算多元一次方程式 1A + 13B + 33C + 43D + 139E + 169F + 1309G + 2597H = I 的非負整數解的數量，其中 I 為輸入。

解題思路

這道題可以使用動態規劃來解決。我們可以建立一個陣列 ans，其中 ans[i] 表示方程式等於 i 的非負整數解的數量。

初始化 ans[0] = 1，表示當 I 為 0 時，只有一種解，即所有變數都為 0。

然後，我們迭代給定的係數 c 陣列，對於每個係數 c[i]，我們更新 ans 陣列。對於每個 j，如果 j + c[i] 不超過 ans 陣列的長度，則 ans[j + c[i]] += ans[j]。這表示我們可以通過將變數 i 的值增加 1，並從 ans[j] 的解中獲得 ans[j + c[i]] 的解。

最後，對於每個輸入 n，我們輸出 ans[n]，即方程式等於 n 的非負整數解的數量。

複雜度分析

• 時間複雜度: O(8000 * 8) (因為有 8 個係數，且迭代到 8000)
• 空間複雜度: O(8001) (用於儲存 ans 陣列)

程式碼

#include <iostream>
using namespace std;
long long int ans[8001]={1};
int c[8]={1,13,33,43,139,169,1309,2597},n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int i=0;i<8;++i){
		for(int j=0;j<=8000;++j){
			if(j+c[i]>8000)break;
			ans[j+c[i]]+=ans[j];
		}
	}
	while(cin >> n)
		cout << ans[n] << "\n";
}