g278 - 4. 美食博覽會

🔗 前往 ZeroJudge 原題

題目描述

題目要求在 $n$ 個攤位的美食中，由 $k$ 個人依序品嚐，每個人選擇一段連續的攤位，且不能重複品嚐同一種美食。目標是最大化所有品嚐員品嚐到的攤位總數。

解題思路

本題可以使用動態規劃來解決。dp[i][j] 表示前 $i$ 個人品嚐美食，且第 $i$ 個人品嚐到第 $j$ 個攤位的最大攤位數。

首先，我們需要預處理每個美食最後出現的位置。f[i] 記錄美食 $i$ 最後出現的攤位位置。

然後，我們使用動態規劃來計算最大攤位數。dp[i&1][j] 表示第 $i$ 個人品嚐到第 $j$ 個攤位的最大攤位數。狀態轉移方程為：dp[i&1][j] = max(dp[i&1][j-1], dp[(i-1)&1][f[j]] + j - f[j])。

最後，我們遍歷所有攤位，找到最大攤位數。

由於 k <= 20，因此可以使用滾動數組優化空間複雜度。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int f[1000005],n,m,c[100005],a,dp[2][1000005],ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int i=1;i<=n;++i){
		cin >> a;
		f[i]=max(c[a],f[i-1]);
		c[a]=i;
	}
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j)
			dp[i&1][j]=max(dp[i&1][j-1],dp[(i-1)&1][f[j]]+j-f[j]);
	for(int i=1;i<=n;++i)
		ans=max(dp[m&1][i],ans);
	cout << ans;
}