백준 11001번 김치

문제 요약

김치를 $i$일에 넣고 $j$일에 꺼낸다면 이 김치의 맛은 $(j-i)T_j+V_i$로 정의된다. $T_j$는 $j$번째 날의 온도이며, $V_i$는 $i$번째 날의 김치의 가치다.

이 때, 최대 D만큼만 김치를 숙성시킬 수 있다. ($j-i\le D$), $T_i,V_i$가 N개만큼 주어질 때 만들 수 있는 최대 김치의 맛을 구해라

N은 최대 10만이다.

풀이

$C(i,j)$를 $i$번째 날에 김치를 넣어서 $j$번째 날에 꺼낸 김치의 맛으로 정하자.
$$C(i,j)=(j-i)T_j+V_i$$
문제의 조건에서 $T_i\ge T_{i+1}$이라고 했다.

넣은 날을 $i$번째 날로 고정했을 때 꺼냈을 때 제일 맛있는 날을 $op{t}_i$라고 하자.

그러면 위 조건 때문에 $i<i^{\prime }$일 때, $op{t}_i,\le op{t}_{i^{\prime }}$임을 증명할 수 있다.

따라서, 분할정복 최적화를 적용할 수 있다. 최대 D일 만큼만 넣을 수 있다는 조건만 주의하자.

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

vector<ll> T, V, dp;
int D, N;
ll ans;
ll cnt;
ll C(ll i, ll j) {
    return V[i] + (j-i) * T[j];
}

void solve(int s, int e, int optl, int optr) {
    if(s > e) return ;
    int mid = (s+e) >> 1;
    int opt = mid;
    dp[mid] = V[mid];
    pair<ll,int> ret = {V[mid],mid};
    for(int i=optl;i<=min(optr, mid+D);++i) {
        ll val = V[mid] + (i - mid) * T[i];
        if(dp[mid] < val) {
            dp[mid] = val; opt = i;
        }
    }
    solve(s, mid-1, optl, opt);
    solve(mid+1, e, opt, optr);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> D;
    T.resize(N+1); V.resize(N+1); dp.resize(N+1);
    for(int i=1;i<=N;++i) cin >> T[i];
    for(int i=1;i<=N;++i) cin >> V[i];
    solve(1,N,1,N);
    for(int i=1;i<=N;++i) ans = max(ans, dp[i]);
    cout << ans << '\n';
    return 0;
}