# 🌱 Lời giải Mely Educational Contest 04 bài H : Rừng cây

>[color=pink] Nếu bạn cảm thấy Edit này chất lượng tiếc gì một upvote và giới thiệu team với mọi người nhé :heart:

###### 📋 Content:
[TOC]
____
## Nhận xét :label:
:question: Với trường hợp **K = 0**, ta có nhận xét : đáp án sẽ là tổng tất cả **max(0,h[i]-h[i-1])** với *(**1** <= **i** <= **n**)* và **h[0] = 0**; chứng minh nhận xét này không khó nên mình sẽ để dành cho các bạn suy nghĩ :D

Với nhận xét trên ta có thể nghĩ tới một thuật toán quy hoạch động như sau :
>[color=green]
>+ gọi ***dp[i][t]*** là đến với vị trí thứ ***i*** (cây thứ ***i*** không thay đổi độ cao) và số cây thay đổi là ***t*** thì phải tốn ít nhất trong bao nhiêu sức mạnh
>+ Giả sử hai cột không thay đổi giá trị liên tiếp là ***j*** và ***i*** thì dễ nhận thấy các cây nằm giữa ***j*** và ***i*** sẽ chuyển hết độ cao về ***h[j]*** hoặc ***h[i]*** do nhận xét ở trên đã trình bày. Nói cách khác ta có thể coi như bỏ qua các nằm giữa ***i*** và ***j***. Từ đây ta có cách chuyển đổi trạng thái :
>+ ***dp[i][t] = max(dp[i][t], dp[j][t-(i-j-1)] + max(0,h[i]-h[j]) )***
>+ Đáp án là ***max(dp[i][t])*** mà ***(t + n – i <= k)***.

Thuật toán này có thể giải dễ dàng với độ phức tạp $O(n^3)$, tuy nhiên để tối ưu xuống $O(n^2log)$ ta cần nhận xét thêm :
>[color=green]
>- ***dp[i][t]*** sẽ được cập nhật từ các trạng thái ***dp[x][y]*** mà **x-y = i-t-1** (giống đường chéo trên bảng); vậy nên các trạng thái này hoàn toàn có thể cập nhật nhanh bằng các lập thêm mảng phụ . Tuy nhiên do còn điều kiện ***max(0,h[i]-h[x])*** do đó chúng ta cần đến ctdl cùng kĩ thuật nén số để kiểm soát 2 trường hợp (mỗi trường hợp dùng 1 cây phân đoạn -> mỗi đường chéo cần xét bằng 2 cây phân đoạn tương ứng) :
>- Nếu ***(h[x] <= h[i])*** thì ***dp[i][t] = (dp[x][y] – h[x])*** + ***h[i]***) -> cây phân đoạn TH1 này sẽ dùng để lấy min các giá trị ***(dp[x][y] – h[x])*** mà ***h[x] <= h[i]***.
>- Nếu ***(h[x] > h[i])*** ***dp[i][t] = dp[x][y] + h[i])*** -> cây phân đoạn TH2 này sẽ dùng để lấy min các giá trị ***(dp[x][y] – h[x])*** mà ***(h[x] > h[i]).***

## Code mẫu :bulb:
> **Time:** $O(n^2log)$
> **Space:** $O(n^2)$
> **Algo:** Dynamic programing.
> [color=lightgreen]
:::success
:::spoiler code mẫu

#include<iostream>
#include<vector>
#include<algorithm>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
//#define int long long
using namespace std;
using ll = long long;
const int maxN = 2e3 + 5;
const int mod = 998244353;
const ll infty = 1e18;

int n,k;
ll dp[2005][2005];
vector<int> unq;
int h[maxN];

struct Segtree
{
    ll st[4*maxN];
    void Init()
    {
        fill(st,st + 4*n + 5,infty);
    }
    void Update(int idx,int l,int r,int i,ll val)
    {
        if(i < l || i > r) return;
        if(l == r)
        {
            st[idx] = min(st[idx],val);
            return;
        }
        int mid = (l + r) / 2;
        Update(idx * 2,l,mid,i,val);
        Update(idx * 2 + 1,mid+1,r,i,val);
        st[idx] = min(st[idx*2],st[idx*2+1]);
    }
    ll Get(int idx,int l,int r,int u,int v)
    {
        if(v < l || u > r) return infty;
        if(u <= l && r <= v)
            return st[idx];
        int mid = (l + r) / 2;
        return min(Get(idx*2,l,mid,u,v),Get(idx*2+1,mid+1,r,u,v));
    }
};

Segtree small[2005],big[2005];

inline int new_val(int x)
{
    return upper_bound(unq.begin(),unq.end(),x) - unq.begin();
}

void Read()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
    {
        cin >> h[i];
        unq.push_back(h[i]);
    }

    for(int i = 0;i <= n;i++)
    {
        small[i].Init();
        big[i].Init();
        for(int j = 0;j <= k;j++)
        {
            dp[i][j] = 1e18;
        }
    }

    unq.push_back(0);
    sort(unq.begin(),unq.end());
    unq.erase(unique(unq.begin(),unq.end()),unq.end());

    dp[0][0] = 0;
    small[0].Update(1,1,n+1,new_val(0),0);
    big[0].Update(1,1,n+1,new_val(0),0);

    for(int i = 1;i <= n;i++)
    {
        dp[i][0] = dp[i-1][0] + max(0,h[i] - h[i-1]);
        small[i].Update(1,1,n+1,new_val(h[i]),dp[i][0]-h[i]);
        big[i].Update(1,1,n+1,new_val(h[i]),dp[i][0]);
    }

    for(int j = 1;j <= k;j++)
    {
        for(int i = 0;i <= n;i++)
        {
            //dp[i][j] = min(dp[i][j],dp[i][j-1]);
            if(i - 1 < j) continue;
            int x = new_val(h[i]);
            dp[i][j] = min(small[i-j-1].Get(1,1,n+1,1,x) + h[i],dp[i][j]);
            dp[i][j] = min(big[i-j-1].Get(1,1,n+1,x+1,n+1),dp[i][j]);
            small[i-j].Update(1,1,n+1,x,dp[i][j]-h[i]);
            big[i-j].Update(1,1,n+1,x,dp[i][j]);
        }
    }

    ll res = 1e18;
    for(int j = 0;j <= k;j++)
    {
        for(int i = 0;i <= n;i++)
        {
            if(j + (n - i) <= k)
            {
                res = min(res,dp[i][j]);
            }
        }
    }
    cout << res;
}

void Solve()
{

}

void Debug()
{
}

int32_t main()
{
    //freopen("32.inp","r",stdin);
    //freopen("test.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

//    int subtask;
    int tt;
    tt = 1;
    //cin >> tt;
    for(int i = 1; i <= tt; i++)
    {
        Read();
        Solve();
        Debug();
    }
}

:::success