b589 - 超級馬拉松賽

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個超級馬拉松比賽，選手可以選擇以正常速度或加速跑完每一段路程。加速跑可以獲得兩倍分數，但下一段路程必須休息，得到 0 分。目標是計算在所有路程中，如何選擇加速跑的策略才能獲得最高的總得分。

解題思路

本題可以使用動態規劃 (Dynamic Programming) 解決。定義 dp[i] 為跑完前 i 段路程所能獲得的最高總得分。對於每一段路程 i，選手有兩種選擇：

1. 正常速度跑完：dp[i] = dp[i-1] + c[i-1]
2. 加速跑完：dp[i] = dp[i-2] * 2 + c[i-2] (因為加速跑完後下一段路程得 0 分，所以實際上是加上 c[i-2] 的兩倍)

最終的答案是 dp[n]，其中 n 是路程的數量。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int main(){
	int n;
	while(cin >> n){
		if(n==0)break;
		int c[n+2],dp[n+2],maxn=0;
		for(int i=0;i<n;++i)
			cin >> c[i];
		c[n]=0;
		c[n+1]=0;
		dp[0]=0;
		dp[1]=c[0];
		for(int i=2;i<n+2;++i){
			dp[i]=max(c[i-2]*2+dp[i-2],dp[i-1]+c[i-1]);
			if(dp[i]>maxn){
				maxn=dp[i];
			}
		}
		cout << maxn << "\n";
	}
}