백준 11001 김치

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

 

DnC opt 연습용으로 유명한 문제.. 인데 사실 DP가 아니다

식을 세워 보니 일차함수식이라 CHT로 풀어보려 했는데 기울기 조건이 안 맞았다

리차오트리를 쓰려고 기억을 더듬어가며 다 짰더니 숙성 기간 <= D 조건 때문에 잘 안 된다..

결국 세그에 리차오를 박아서 풀었다. 메모리 괜찮을까 싶었는데 널널하게 돌아간다

 

DnC opt도 그렇고 monge를 요구하는 dp최적화들은 발상이 어떻게 나오는지 잘 모르겠다. 유형이 눈에 익으면 문제에서 monge스러움이 유추되나 싶은데, 유형이 눈에 익으려면 이런 문제를 많이 풀어봐야 하고 monge함을 모르면 문제를 많이 못 풀고 어케연습하는거지

먼가 기울기 조건 맞게 식을 잘 만지면 CHT로도 풀린다는 것 같은데.. 모르겠다

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll V[101010], T[101010], N, D;
 
struct Node {
    int ma, li, ri;
    Node() {}
    Node(int ma, int li, int ri) : ma(ma), li(li), ri(ri) {}
    ll get(ll x) {
        return -ma*x + V[ma];
    }
};
 
struct Lichao {
    vector<Node> seg;
    int sz;
    Lichao() {
        sz = 1e9;
        seg.emplace_back(0, -1, -1);
    }
    void update(int now, int l, int r, int i) {
        auto get = [&](ll x) {
            return -i * x + V[i];
        };
        if (l == r) {
            if (seg[now].get(l) >= get(l))
                seg[now].ma = i;
            return;
        }
        int m = l+r >> 1;
        if (seg[now].li == -1) {
            seg[now].li = seg.size();
            seg.emplace_back(seg[now].ma, -1, -1);
        }
        if (seg[now].ri == -1) {
            seg[now].ri = seg.size();
            seg.emplace_back(seg[now].ma, -1, -1);
        }
        ll lv = seg[now].get(l), rv = seg[now].get(r), mv = seg[now].get(m);
        ll nlv = get(l), nrv = get(r), nmv = get(m);
        if (lv >= nlv and rv >= nrv) return;
        if (lv <= nlv and rv <= nrv)
            seg[now].ma = i;
        else if (lv <= nlv){
            if (mv <= nmv){
                update(seg[now].ri, m+1, r, seg[now].ma);
                seg[now].ma = i;
            }
            else 
                update(seg[now].li, l, m, i);
        }
        else {
            if (mv <= nmv){
                update(seg[now].li, l, m, seg[now].ma);
                seg[now].ma = i;
            }
            else
                update(seg[now].ri, m+1, r, i);
        }
    } 
    void add(int i) {
        update(0, 0, sz, i);
    }
    ll query(ll x) {
        ll l = 0, r = sz, ans = -1e18;
        int now = 0;
        while (now != -1) {
            ans = max(ans, seg[now].get(x));
            ll m = l+r >> 1;
            if (x <= m) r = m, now = seg[now].li;
            else l = m+1, now = seg[now].ri;
        }
        return ans;
    }
} seg[101010 << 2];
 
void update(int i) {
    int l = 1, r = N, now = 1;
    seg[now].add(i);
    if (N == 1) return;
    do {
        int m = l+r >> 1;
        if (i <= m) r = m, now *= 2;
        else l = m+1, now = now*2+1;
        seg[now].add(i);
    } while (l != r);
}
 
ll query(int now, int l, int r, int s, int e, int x) {
    if (e < l or r < s) return -1e18;
    if (s <= l and r <= e) return seg[now].query(x);
    int m = l+r >> 1;
    return max(query(now*2,l,m,s,e,x), query(now*2+1,m+1,r,s,e,x));
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> N >> D;
    for (int i = 1; i <= N; i++) cin >> T[i];
    for (int i = 1; i <= N; i++) cin >> V[i];
    V[0] = -1e18;
    ll ans = -1e18;
    for (int i = 1; i <= N; i++) {
        update(i);
        ans = max(ans, query(1,1,N,max(i-D,1LL),i,T[i]) + T[i]*i);
    }
    cout << ans;
}