Proficient.
Put your skills to the test.

Problem summary

Choose maintenance checkpoints of minimum total cost, skipping at most two consecutive checkpoints and stopping at least once.

Constraints

1 ≤ N ≤ 1000; 1 ≤ cost < 100.

Worked example

An independently prepared example for this explanation.

7
3 4 10 15 12 2 8

12

Solution analysis

1. Let dp[i] be the minimum cost of a valid partial journey whose most recent stop is checkpoint i. Consecutive stops can be at most three positions apart.
2. The first stop can be any of checkpoints 1,2,3. Therefore dp[i]=cost[i] for these possible first stops, or cost[i]+min(dp[i−1],dp[i−2],dp[i−3]) when continuing a journey. The last stop must be among the last three checkpoints.
3. For the sample, stopping at checkpoints 3 and 6 costs 10+2=12. There are two skipped checkpoints initially and between these stops, and one after the final stop, so the route is valid.

Why it works

Every valid journey ending at i either begins there with i≤3, or has a previous stop among i−3,i−2,i−1. The recurrence enumerates exactly those alternatives, and appending i preserves the skipping rule. Choosing among final stops at most two positions before the end ensures a complete valid journey.

Watch out. The initial and final skipped runs also have length at most two. For N≤2 a stop is still mandatory.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Let dp[i] be the minimum cost of a valid partial journey whose most recent stop is
// checkpoint i.
using namespace std;
int main(){
    int n;
    cin>>n;
    const int infinity=1000000000;
    vector<int>dp(n+1,infinity);
    for(int i=1;i<=n;++i){
        int cost;
        cin>>cost;
        if(i<=3){
            dp[i]=cost;
        }
        for(int previous=max(1,i-3);previous<i;++previous){
            dp[i]=min(dp[i],dp[previous]+cost);
        }
    }
    int answer=infinity;
    for(int last=max(1,n-2);last<=n;++last){
        answer=min(answer,dp[last]);
    }
    cout<<answer<<'\n';
}