백준 2616 소형기관차

 

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

2616번: 소형기관차

비교적 쉬운 dp였습니다. 기차의 길이가 정해져있기때문에 현재에서 기차 길이 이전만큼 위치의 최대값을 참조하여 현재 위치를 끝으로 기차를 한대 세운 값과 현재위치의 기차를 세우지않은 값(바로 전위치까지의 최대값)을 비교하여 dp배열에 기록하여 풀 수 있습니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<stack>
using namespace std;
int dp[80000][3];
int arr[80000];
int ps[80000];
int main(){
    int N,M;
    cin>>N;
    int solve=-2e9;
    int s=20000;
    int temp=0;
    for(int x=s;x<N+s;x++){
        cin>>arr[x];
        temp+=arr[x];
        ps[x]=temp;
    }
    cin>>M;
    for(int x=s;x<N+s;x++){
        dp[x][0]=max(dp[x-1][0],ps[x]-ps[x-M]);
        dp[x][1]=max(dp[x-1][1],dp[x-M][0]+ps[x]-ps[x-M]);
        dp[x][2]=max(dp[x-1][2],dp[x-M][1]+ps[x]-ps[x-M]);
        solve=max(dp[x][2],solve);
    }
    cout<<solve;
}