백준 BOJ 2616 소형기관차

i 번째의 값은
지금까지의 최대값 (i-1)  vs i-m + 구간합 (presum[i]-presum[i-m]) 으로 정해진다.

 

즉 dp[i][kk] // i번째 칸,  kk는 소형기관차 개수 , m은 최대 칸 수  

dp[i][kk] = max (dp[i-1][kk], dp[i-m][kk-1] + presum[i] - presum[i-m])

 

( kk==0 은 0으로 둔다.)

 

 

#include<iostream>
#include<memory.h>
#include<vector>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<string>
#include<cmath>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
int n, m, k;
 
int a[50001];
int dp[50001][4];
int presum[50001];
 
int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
 
    scanf("%d", &m);
 
    presum[0] = a[0];
    for (int i = 1; i < n; i++) {
        presum[i] = presum[i - 1] + a[i];
    }
 
    memset(dp, 0, sizeof(dp));
 
    for (int kk = 1; kk < 4;kk++) {
        for (int i = kk * m-1; i < n; i++) {
            dp[i][kk] = max(dp[i-1][kk], dp[i-m][kk-1] + presum[i] - presum[i - m]);
        }
    }
 
    
    printf("%d\n", dp[n - 1][3]);
 
 
    return 0;
}