[백준] 3233 - BRODOVI (c++)

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

Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Seniors 4번

 

문제 요약

N크기의 강에 칸 마다 물고기에 개수가 주어진다. M개의 닻을 내릴 위치와 배의 크기가 주어질 때 배를 닻에서 벗어나지 않게 옮겨서 잡을 수 있는 물고기의 최댓값을 구해라.

 

풀이 (MlogM)

• 스위핑
• DP
• 누적합

닻을 스위핑하면서 1차원 DP배열을 업데이트 해주면 된다. 배가 서로 겹칠 수 없기 때문에 현재 배가 전,후 닻까지 가지 못하게 하고 범위안에서 누적합으로 잡을 수 있는 물고기를 구해 업데이트 해준다. 배가 가지 못하는 곳도 생기기 때문에 갱신 했던 마지막 위치 부터 현재위치까지 dp를 최댓값으로 업데이트 해주는 것도 필요하다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n;
    int s[n+1]{};
    for(int i=1,x;i<=n;i++)
        cin>>x,s[i]=s[i-1]+x;
    cin>>m;
    array<int,2> a[m];
    for(auto& [x,y]:a)cin>>x>>y;
    sort(a,a+m);

    int dp[n+1]{},l=0;
    for(int i=0;i<m;i++) {
        auto [x,y]=a[i];
        for(;l+1<x;l++)dp[l+1]=max(dp[l+1],dp[l]);

        int lst=i==0?0:a[i-1][0],nxt=i==m-1?n+1:a[i+1][0];
        for(int j=max(x,lst+y);j<x+y&&j<nxt;j++)
            dp[j]=max(dp[j],dp[j-y]+s[j]-s[j-y]);
    }
    cout<<*max_element(dp+l,dp+n+1);
}