b595 - Special Touring Car Racing
題目描述
題目描述了一場特殊的房車賽，參賽者需要在若干個停車區域中選擇停靠點，最終到達終點。目標是最小化每日行駛距離與理想距離 200 之間的差的平方和，以此最小化總罰金。
解題思路
本題可以使用動態規劃來解決。dp[i] 表示到達第 i 個停車區域所需的最小罰金。對於每個停車區域 i，我們遍歷之前的停車區域 j，計算從 j 到 i 的行駛距離 x，並計算對應的罰金 (200 - x)^2。dp[i] 的值是所有可能的 j 中，dp[j] + (200 - x)^2 的最小值。gt[i] 記錄了到達 i 最小罰金的前一個停車區域，用於回溯最佳路徑。最後，從終點開始回溯，重建最佳路徑並輸出。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是停車區域的數量。因為需要遍歷所有可能的停車區域組合。
- 空間複雜度: O(n)，用於儲存
dp、gt和ans陣列。
程式碼
#include<bits/stdc++.h>
using namespace std;
long long n,a[10005],dp[10005],gt[10005],ans[10005];
int main(){
cin.tie(0); ios::sync_with_stdio(0);
while(cin >> n){
if(n==0)break;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;++i){
cin >> a[i];
for(int j=0;j<i;++j){
if(dp[j]+(200-a[i]+a[j])*(200-a[i]+a[j])<dp[i]){
dp[i]=dp[j]+(200-a[i]+a[j])*(200-a[i]+a[j]);
gt[i]=j;
}
}
}
int sz=0,it=n;
while(it){
ans[sz++]=it;
it=gt[it];
}
cout << "0 ";
for(int i=sz-1;i>=0;--i){
cout << ans[i] << " ";
}
cout << "\n";
}
}