[BOJ 11001] 김치

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

11001번: 김치

Tag : dnc opt

 

문제요약

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

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

$D_i=ma{x}_{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}\le (P(i+1)-(i+1))\times T_{P(i+1)}+V_{i+1}$

 

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

 

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

 

$\frac{P(i)-(i+1)}{P(i+1)-(i+1)}\le \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)\le P(i)$가되고 이는 $P(i)>P(i+1)$에 모순된다. 

따라서 $P(i)\le 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;
}