2616 소형기관차

백준 2616 소형기관차 https://www.acmicpc.net/problem/2616

소형기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 문제이다.

$DP[N][M]$ : 소형기관차를 N대 운행할 때 M번째 객차를 선택했을 경우의 최대 운송 손님 수(기관차에 K개의 객실을 넣을 때)

배열 $S[N]$을 이용해 N번째 객차까지의 손님 수를 모두 더
해 놓는다.

$S[N] = S[N-1]+arr[N]$

이렇게 해놓으면 나중에 N번째 객차에 해당하는 기관차의 손님수를 바로 알 수 있다.
$S[N]-S[N-K]$


$DP[N][M] = max(DP[N][M-1], DP[N - 1][M - K] + S[M]-S[M-K]$

                                                                                   <문제 예시의 DP값>
따로 점화식에 대한 풀이는 하지 않겠다.

#include <cstdio> #include <algorithm> using namespace std; int arr[50001];     int S[50001]; int dp[4][50001]; int main(){     int N, K;     int ans = 0;     scanf("%d", &N);     for (int n = 1; n <= N; n++){         scanf("%d", &arr[n]);         S[n] = S[n - 1] + arr[n];       }     scanf("%d", &K);     for (int n = 1; n <= 3; n++){         for (int m = n*K; m <= N; m++){             if (n == 1)                 dp[n][m] = max(dp[n][m-1], S[m] - S[m - K]);             else                 dp[n][m] = max(dp[n][m-1],dp[n - 1][m - K] + S[m]-S[m-K]);                          ans = max(ans, dp[n][m]);         }     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs