【題解】Codeforces Gym 102059G. Fascination Street

#include <iostream>
#include <cstring>
using namespace std;
 
int n, m, a[250005];
long long dp[250005][3][10][10], ans = 1e18;
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][1][0][0] = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < 3; j++){
            for (int k = 0; k <= m; k++){
                for (int l = 0; l <= m; l++){
                    if (j != 2){
                        dp[i+1][j+1][k][l] = min(dp[i+1][j+1][k][l], dp[i][j][k][l]);
                        if (l != m) dp[i+1][j+1][k][l+1] = min(dp[i+1][j+1][k][l+1], dp[i][j][k][l]+a[i+1]);
                    }
                    dp[i+1][0][k][l] = min(dp[i+1][0][k][l], dp[i][j][k][l]+a[i+1]);
                    if (k != m) dp[i+1][0][k+1][l] = min(dp[i+1][0][k+1][l], dp[i][j][k][l]);
                }
            }
        }
    }
    for (int j = 0; j < 2; j++){
        for (int k = 0; k <= m; k++){
            ans = min(ans, dp[n][j][k][k]);
        }
    }
    cout << ans << "\n";
}