정올이의 모의고사 (JUNGOL 5092)

https://jungol.co.kr/problem/5092?cursor=MTMsMCw0

---

아이디어

만약 풀 문제를 정했다면, 어떤 순서대로 푸는것이 이득일까요? 이는 Exchange Argument로 최적화해줄 수 있습니다.

 

i번째 문제를 풀기 시작한 시각을 t라하면, i번째 문제를 푼 시각과 i+1번째 문제를 풀기 시작한 시각은 t+R_i이라고할 수 있고, i+1번째 문제를 푼 시각은 t+R_i+R_i+1이라고 할 수 있습니다. 이때의 점수는 (M_i-(t+R_i)P_i)+(M_i+1-(t+R_i+R_i+1)P_i+1)이라고 할 수 있습니다. 이때 두 문제의 푸는 순서를 바꾸면 점수가 (M_i+1-(t+R_i+1)P_i+1)+(M_i-(t+R_i+R_i+1)P_i)가 되며, 앞에 식이 더 크거나 같아야하므로 정리하면 R/P가 증가하는 순서대로 문제를 해결해주면 됩니다.

 

그러면 모든 문제를 정렬할 수 있게 됩니다. 여기서 dp[i][j]를 i번 문제까지 푸는데에 j의 시간이 걸렸을 때의 점수의 최댓값이라고 정의합시다. 이 dp테이블을 채워주면 문제를 해결할 수 있습니다.

---

소스코드

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

ll dp[55][101010]={0};

bool cmp(array <ll,3> A,array <ll,3> B) //{M,P,R}
{
    return A[1]*B[2]>A[2]*B[1];
}

ll M[101010]={0},P[101010]={0},R[101010]={0};

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,T,i,j;

    cin>>N>>T;
    for (i=1;i<=N;i++) cin>>M[i];
    for (i=1;i<=N;i++) cin>>P[i];
    for (i=1;i<=N;i++) cin>>R[i];

    vector <array <ll,3> > v;
    v.push_back({0,0,0});
    for (i=1;i<=N;i++)
        v.push_back({M[i],P[i],R[i]});

    sort (v.begin()+1,v.end(),cmp);

    for (i=1;i<=N;i++)
    {
        for (j=1;j<=T;j++)
        {
            dp[i][j]=dp[i-1][j];
            if (j>=v[i][2])
                dp[i][j]=max(dp[i][j],dp[i-1][j-v[i][2]]+v[i][0]-j*v[i][1]);
        }
    }

    ll res=0;
    for (i=1;i<=T;i++)
        res=max(res,dp[N][i]);

    cout<<res;
}