b595. Special Touring Car Racing

---

解法一、DP

✅ 完整代碼

評分結果(參考) ： AC (1ms, 324KB)

#include<bits/stdc++.h>
#define int long long
using namespace std;

int cost(int a1, int a2){
    return pow(200-abs(a1-a2), 2);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while(true) {
        cin >> n;
        if(n == 0) break;
        
        vector<int> a(n+1);
        a[0] = 0;
        for(int i=1; i<=n; i++){
            cin >> a[i];
        }
        
        vector<int> dp(n+1, 1e18);
        vector<int> prev(n+1, -1);
        dp[0] = 0;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<=n; j++){
                int temp = dp[i] + cost(a[i], a[j]);
                if(temp < dp[j]){
                    dp[j] = temp;
                    prev[j] = i;
                }
            }
        }
        
        vector<int> ans;
        int k = n;
        while(k != -1){
            ans.push_back(k);
            k = prev[k];
        }
        
        for(int i=ans.size()-1; i>=0; i--){
            cout << ans[i] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}