dp_pathdomin.cpp

dp_pathdomin.cpp

#include <bits/stdc++.h>

using namespace std;

int solve(int n)
{
    int dp[n][3];

    int inp[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &inp[i]);
        dp[i][0] = dp[i][1] = dp[i][2] = INT_MAX;
    }

    if (n == 1)
        return inp[0];

    dp[0][0] = inp[0];
    dp[0][1] = 0;
    for (int i = 1; i < n; i++) {
        dp[i][0] = min(dp[i][0], min(dp[i - 1][1], dp[i - 1][0]) + inp[i]);
        dp[i][1] = dp[i - 1][0];

        if (i != n - 1 && i - 2 >= 0) {
            dp[i][2] = dp[i - 2][0] + inp[i + 1];
            dp[i + 1][0] = dp[i][2];
        }
    }

    /*
    for (int j = 0; j < 3; j++)
        for (int i = 0; i < n; i++)
            printf("%10d%c", dp[i][j], i == n - 1 ? '\n' : ' ');
    */

    return min(dp[n - 1][0], dp[n - 1][1]);
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1 && n) {
        printf("%d\n", solve(n));
    }

    return 0;
}