Metro Profile
National Olympiad — National round
Submission name: metro.cpp
Problem summary
Choose integer track heights along n terrain positions. Between neighboring positions the height may change by −2, −1, 0, or +1. At a position with terrain height h, track height z costs 7(z−h) above ground, (h−z)² below ground, and 1 on the surface. Minimize the total cost; endpoints are unrestricted.
Input
n, then n terrain heights in order.
Output
The minimum total cost.
Constraints
1 ≤ n < 1000; terrain heights are positive integers smaller than 100.
Worked example
An independently prepared example for this explanation.
Input
3 5 5 5
Output
3
Solution analysis
- Use dp[z] for the minimum cost of the prefix ending at height z.
- A transition from height p to z is legal exactly when −2≤z−p≤1. Add the cost at the new position.
- Only heights between the minimum and maximum terrain height are needed: clamping any profile to that interval preserves allowed differences and never increases point costs.
Why it works
The last transition and height determine all information needed from a prefix, so the DP checks every feasible profile. Clamping below or above the terrain range moves track towards every terrain height and preserves the directed step bounds; even the surface cost 1 does not exceed the cost of an adjacent off-surface integer height.
Watch out. Flat movement is allowed. Above-ground and below-ground prices differ. No fixed endpoint heights are imposed.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The last transition and height determine all information needed from a prefix, so the DP
// checks every feasible profile. Clamping below or above the terrain range moves track towards every
// terrain height and preserves the directed step bounds; even the surface cost 1 does not exceed the
// cost of an adjacent off-surface integer height.
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int&x:a){
cin>>x;
}
int lo=*min_element(a.begin(),a.end()),hi=*max_element(a.begin(),a.end());
auto cost=[](int z,int h){
return z==h?1:z>h?7*(z-h):(h-z)*(h-z);
};
const int INF=1000000000;
vector<int>dp(hi+1,INF);
for(int z=lo;z<=hi;z++){
dp[z]=cost(z,a[0]);
}
for(int i=1;i<n;i++){
vector<int>next(hi+1,INF);
for(int z=lo;z<=hi;z++){
for(int p=max(lo,z-1);p<=min(hi,z+2);p++){
next[z]=min(next[z],dp[p]+cost(z,a[i]));
}
}
dp.swap(next);
}
cout<<*min_element(dp.begin()+lo,dp.end())<<'\n';
}