[DP] 백준 1757 달려달려 C++

 

https://www.acmicpc.net/problem/1757

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 1000001
using namespace std;

int n, m, a;
int dp[10001][501][2];
vector<int> v;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    v.push_back(0);
    for (int i = 0; i < n; i++) {
        cin >> a;
        v.push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j != 1) {
                if (j > 0) {
                    dp[i][j][1] = dp[i - 1][j - 1][1] + v[i];
                    dp[i][j][0] = max(dp[i - 1][j + 1][1], dp[i - 1][j + 1][0]);
                }
                else {
                    dp[i][j][0] = max({ dp[i - 1][j + 1][0], dp[i - 1][j + 1][1], dp[i - 1][j][0] });
                }
            }
            else {
                dp[i][j][1] = dp[i - 1][j - 1][0] + v[i];
                dp[i][j][0] = max(dp[i - 1][j + 1][1], dp[i - 1][j + 1][0]);
            }
        }
    }

    cout << dp[n][0][0];
}