CF E

题目：传送门

题意

给你一个长度为 n 的序列 a，你有两种操作：

1.选择一段区间 [l, r] 满足区间内所有数都大于 0，对区间内每个数减 1

2.选择一个 i 和 x，让 a[i] = a[i] - x

问最少需要操作多少次，使得序列所有数都变为 0

1 <= n <= 5000; 0 <= ai <= 1e9

思路

一. DP

dp[i][j]：处理完序列前 i 个数，用了 j 次操作 1 的答案

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x) & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

int n;

int dp[5005][5005];

int a[5005];

void solve() {

    scanf("%d", &n);

    rep(i, 1, n) scanf("%d", &a[i]);

    mem(dp, INF);

    rep(i, 1, n) dp[0][min(a[i], i)] = min(a[i], i);

    dp[0][0] = 0;

    rep(i, 1, n) {

        rep(j, 0, n) {

            dp[i][min(a[i], j)] = min(dp[i][min(a[i], j)], dp[i - 1][j] + 1);

            if(a[i] <= n) {

                if(a[i] <= j) {

                    dp[i][a[i]] = min(dp[i][a[i]], dp[i - 1][j]);

                }

                else {

                    dp[i][a[i]] = min(dp[i][a[i]], dp[i - 1][j] + a[i] - j);

                }

            }

        }

    }

    int ans = INF;

    rep(i, 0, n) ans = min(ans, dp[n][i]);

    printf("%d
", ans);

}


int main() {

//    int _; scanf("%d", &_);
//    while(_--) solve();

    solve();

    return 0;
}

二.分治O(n^2)

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x) & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

const LL mod = 1e9 + 7;

int n;

LL a[N];

LL cal(int l, int r) {

    if(l > r) return 0;

    if(l == r) return min(a[l], 1LL);

    LL mi = a[l]; int pos = l;

    rep(i, l, r) {

        if(a[i] < mi) {

            mi = a[i];

            pos = i;

        }

    }

    rep(i, l, r) {

        a[i] -= mi;

    }

    return min(cal(l, pos - 1) + cal(pos + 1, r) + mi, 1LL * (r - l + 1));

}

void solve() {

    scanf("%d", &n);

    rep(i, 1, n) scanf("%lld", &a[i]);

    printf("%lld
", cal(1, n));

}


int main() {

//    int _; scanf("%d", &_);
//    while(_--) solve();

    solve();

    return 0;
}

三.分治O(nlogn)，线段树优化

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define UI unsigned int
#define mem(i, j) memset(i, j, sizeof(i))
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dep(i, j, k) for(int i = k; i >= j; i--)
#define pb push_back
#define make make_pair
#define INF 0x3f3f3f3f
#define inf LLONG_MAX
#define PI acos(-1)
#define fir first
#define sec second
#define lb(x) ((x) & (-(x)))
#define dbg(x) cout<<#x<<" = "<<x<<endl;
using namespace std;

const int N = 1e6 + 5;

const LL mod = 1e9 + 7;

int n;

int a[N];

struct note {

    int x, lz, id;

}t[N];

void build(int rt, int l, int r) {

    if(l == r) {

        t[rt].x = a[l];

        t[rt].id = l;

        t[rt].lz = 0;

        return ;

    }

    int mid = (l + r) >> 1;

    build(rt << 1, l, mid);

    build(rt << 1 | 1, mid + 1, r);

    if(t[rt << 1].x <= t[rt << 1 | 1].x) {

        t[rt].x = t[rt << 1].x;

        t[rt].lz = t[rt << 1].lz;

        t[rt].id = t[rt << 1].id;

    }

    else {

        t[rt].x = t[rt << 1 | 1].x;

        t[rt].lz = t[rt << 1 | 1].lz;

        t[rt].id = t[rt << 1 | 1].id;

    }

}

void pushdown(int rt) {

    if(t[rt].lz) {

        t[rt << 1].x -= t[rt].lz;

        t[rt << 1 | 1].x -= t[rt].lz;

        t[rt << 1].lz = t[rt].lz;

        t[rt << 1 | 1].lz = t[rt].lz;

        t[rt].lz = 0;

    }

}

note query(int rt, int l, int r, int L, int R) {

    if(L <= l && r <= R) return t[rt];

    pushdown(rt);

    int mid = (l + r) >> 1;

    note ans;

    ans.x = INF; ans.id = 0; ans.lz = 0;

    if(L <= mid) {

        note tmp = query(rt << 1, l, mid, L, R);

        if(tmp.x < ans.x) ans.x = tmp.x, ans.id = tmp.id;

    }

    if(R > mid) {

        note tmp = query(rt << 1 | 1, mid + 1, r, L, R);

        if(tmp.x < ans.x) ans.x = tmp.x, ans.id = tmp.id;

    }

    return ans;

}

void update(int rt, int l, int r, int L, int R, int d) {

    if(L <= l && r <= R) {

        t[rt].x -= d;

        t[rt].lz += d;

        return ;

    }

    pushdown(rt);

    int mid = (l + r) >> 1;

    if(L <= mid) update(rt << 1, l, mid, L, R, d);

    if(R > mid) update(rt << 1 | 1, mid + 1, r, L, R, d);

    if(t[rt << 1].x <= t[rt << 1 | 1].x) {

        t[rt].x = t[rt << 1].x;

        t[rt].id = t[rt << 1].id;

    }

    else {

        t[rt].x = t[rt << 1 | 1].x;

        t[rt].id = t[rt << 1 | 1].id;

    }

}

int cal(int l, int r) {

    if(l > r) return 0;

    if(l == r) {

        note now = query(1, 1, n, l, r);

        if(now.x) return 1;

        else return 0;

    }

    note now = query(1, 1, n, l, r);

    update(1, 1, n, l, r, now.x);

    return min(cal(l, now.id - 1) + cal(now.id + 1, r) + now.x, (r - l + 1));

}

void solve() {

    scanf("%d", &n);

    rep(i, 1, n) scanf("%d", &a[i]);

    build(1, 1, n);

    printf("%d
", cal(1, n));

}


int main() {

//    int _; scanf("%d", &_);
//    while(_--) solve();

    solve();

    return 0;
}