[BOJ 11001] 김치

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

11001번: 김치

Tag : dnc opt

 

문제요약

(숙성시간)*(꺼낼 때의 온도)+(넣은 날의 가치)의 최대를 구하는 문제다.

\(D_i:=i\)일에 넣었을 때 최대"라 정의하고 문제가 요구하는 대로 식을 세우면 

\(D_i=max_{i<=j<=n}((j-i+1) \times T_j+V_i)\)가 된다. 이를 구하기 위해선 i마다 \(O(N)\)번의 loop를 돌아야하기 때문에

\(O(N^2)\)의 시간복잡도를 가진다. 

 

dnc opt(분할정복 최적화)를 사용하면 이를 \(O(nlogn)\)에 구할 수 있다.

\(P(i):=i\)에서 시작할 때 \(D_i\)를 최대화하는 \(j\)

P의 정의가 위와 같을 때 \(P(i)<=P(i+1)\)임을 보일 수 있다.

 

proof)

P의 정의에 의해 다음 식이 성립한다.

 

\( (P(i)-(i+1)) \times T_{P(i)} + V_{i+1} \leq(P(i+1)-(i+1)) \times T_{P(i+1)}+V_{i+1} \)

 

이를 정리하면 아래와 같다.

 

\( (P(i)-(i+1)) \times T_{P(i)} \leq (P(i+1)-(i+1)) \times T_{P(i+1)} \)

 

\( \frac{P(i)-(i+1)}{P(i+1)-(i+1)} \leq \frac{T_{P(i+1)}}{T_{P(i)}} \)

 

\(P(i)>P(i+1)\)이라면 \( \frac{P(i)-(i+1)}{P(i+1)-(i+1)}\)는 1보다 큰 수가 되고 \(\frac{T_{P(i+1)}}{T_{P(i)}} \)는 이보다 커야하기 때문에 \(T_{P(i+1)} > T_{P(i)}\)이다. T는 단조감소한다는 조건에 따라 \(P(i+1)\leq P(i)\)가되고 이는 \(P(i)>P(i+1)\)에 모순된다. 

따라서 \(P(i)\leq P(i+1)\)이다.

 

(그냥 monge array인거 보이는게 낫다)

 

+ 맞은사람 1등먹었다 뿌듯

 

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

ll N,D;
ll T[101010];
ll v[101010];
ll P[101010];
ll dp[101010];

void dnc(ll s,ll e,ll l,ll r){
    if(s>e)return;
    ll m=(s+e)/2;
    for(ll i=max(l,m);i<=min(r,m+D);i++){
        if((i-m)*T[i]+v[m]>dp[m]){
            dp[m]=(i-m)*T[i]+v[m];
            P[m]=i;
        }
    }
    dnc(s,m-1,l,P[m]);
    dnc(m+1,e,P[m],r);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N>>D;
    for(int i=1;i<=N;i++)cin>>T[i];
    for(int i=1;i<=N;i++)cin>>v[i];
    dnc(1,N,1,N);
    cout<<*max_element(dp+1,dp+N+1)<<endl;
}