e721 - 108北二7.奪寶奇謀

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個奪寶遊戲，有 500 個寶箱，每個寶箱有不同的價值。玩家可以選擇打開寶箱，但打開寶箱的代價是必須跳過下一個寶箱。目標是最大化獲得的總價值。輸入包含 N 個數字，代表玩家打開的寶箱編號。

解題思路

這題可以使用動態規劃來解決。定義 dp[i][0] 為不打開第 i 個寶箱時的最大價值，dp[i][1] 為打開第 i 個寶箱時的最大價值。

• dp[i][0] = max(dp[i-1][0], dp[i-1][1]): 如果不打開第 i 個寶箱，則最大價值等於打開或不打開第 i-1 個寶箱時的最大價值。
• dp[i][1] = a[i] * i + max(dp[i-2][1], dp[i-1][0]): 如果打開第 i 個寶箱，則最大價值等於第 i 個寶箱的價值乘以寶箱編號 i，加上打開或不打開第 i-2 個寶箱時的最大價值（因為打開第 i 個寶箱會跳過第 i+1 個寶箱）。

初始化 dp[0][0] = 0 和 dp[0][1] = 0。最後，答案是 max(dp[500][0], dp[500][1])。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int dp[501][2],n,k,a[501];
int main(){
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> k;
		++a[k];
	}
	for(int i=1;i<501;++i){
		dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
		if(i==1)
			dp[i][1] = a[i];
		else
			dp[i][1] = a[i]*i+max(dp[i-2][1],dp[i-1][0]);
	}
	cout << max(dp[500][0],dp[500][1]); 
}