d389 - 11069 - A Graph Problem

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個特定圖形中，滿足特定條件的節點子集合的數量。該圖形具有 n 個節點，條件是子集合中不能包含相鄰的節點，且不能存在可以再加入一個節點而不與子集合中任何節點相鄰的情況。題目給出 n=5 時的例子，並要求計算對於給定的 n，滿足條件的子集合數量。

解題思路

題目描述的圖形實際上是一個固定的圖形，可以觀察到其結構特性。對於 n=1, 2, 3, 4, 5...，合法的集合數量呈現一個特定的序列。觀察序列 1, 2, 2, 4, 4... 可以發現，這個序列可以通過遞迴關係來定義。具體來說，ans[i] = ans[i-2] + ans[i-3]。程式碼中預先計算了 ans 數組的前 77 項，然後對於輸入的 k，直接輸出 ans[k]。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
long long int ans[88]={0,1,2,2},k;
int main(){
	for(int i=4;i<77;++i){
		ans[i]=ans[i-2]+ans[i-3];
	}
	while(cin >> k){
		cout << ans[k] << "\n";
	}
}