공룡타이쿤 2 (JUNGOL 12222)

https://jungol.co.kr/problem/12222?cursor=NTA4LDEsNw==

---

아이디어

dp[i][j][k][l]을 1번부터 i번째까지 칸까지 봤을 때 햄버거 가게를 j개, 음료수 가게를 k개, 기념품 가게를 l개 골랐을 때의 최대로 만족시킬 수 있는 공룡의 마릿수라고 정의합시다. 그리고 누적합을 통해서 어떠한 구간에 있는 특정 수의 개수를 O(1)에 구해줍시다. 그러면 dp테이블을 채워줄 수 있습니다.

 

그리고 dp[N]값을 보면서 최대한 많은 공룡을 만족시키고, 그러한 경우의 수가 여러 개 있다면, 매장을 최소한으로 사용하는 경우를 구해주어야합니다. dp[N]의 값을 보면서 그러한 값을 찾고 역추적을 통해 어느 위치에 가게를 놓을지 정해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll N,Sum[4][101010]={0};
ll dp[101010][2][2][2]={0};

ll GetSum(ll l,ll r,ll num)
{
    return Sum[num][min(N,r)]-Sum[num][max(l-1,(ll)(0))];
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll D1,D2,D3,i,x;

    cin>>N>>D1>>D2>>D3;
    for (i=1;i<=N;i++)
    {
        cin>>x;
        for (ll j=0;j<=3;j++)
            Sum[j][i]=Sum[j][i-1];
        Sum[x][i]++;
    }

    for (i=1;i<=N;i++)
    {
        for (ll j=0;j<=1;j++)
        {
            for (ll k=0;k<=1;k++)
            {
                for (ll l=0;l<=1;l++)
                {
                    dp[i][j][k][l]=dp[i-1][j][k][l];
                    if (j==1) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j-1][k][l]+GetSum(i-D1,i+D1,1));
                    if (k==1) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k-1][l]+GetSum(i-D2,i+D2,2));
                    if (l==1) dp[i][j][k][l]=max(dp[i][j][k][l],dp[i-1][j][k][l-1]+GetSum(i-D3,i+D3,3));

                    //cout<<"dp["<<i<<"]["<<j<<"]["<<k<<"]["<<l<<"]="<<dp[i][j][k][l]<<"\n";
                }
            }
        }
    }

    ll mx=0,Count=0,a,b,c;
    for (ll j=0;j<=1;j++)
        for (ll k=0;k<=1;k++)
            for (ll l=0;l<=1;l++)
            {
                if (dp[N][j][k][l]>mx)
                {
                    mx=dp[N][j][k][l];
                    Count=j+k+l;
                    a=j,b=k,c=l;
                }
                else if (dp[N][j][k][l]==mx)
                {
                    Count=min(Count,j+k+l);
                    if (Count==j+k+l) a=j,b=k,c=l;
                }
            }

    ll Ans1=-1,Ans2=-1,Ans3=-1;
    for (ll i=N;i>=1;i--)
    {
        if (dp[i][a][b][c]==dp[i-1][a][b][c]) continue;
        if (a && dp[i][a][b][c]==dp[i-1][a-1][b][c]+GetSum(i-D1,i+D1,1)) Ans1=i,a--;
        else if (b && dp[i][a][b][c]==dp[i-1][a][b-1][c]+GetSum(i-D2,i+D2,2)) Ans2=i,b--;
        else if (c && dp[i][a][b][c]==dp[i-1][a][b][c-1]+GetSum(i-D3,i+D3,3)) Ans3=i,c--;
    }

    cout<<Ans1<<' '<<Ans2<<' '<<Ans3;
}