分层图单调决策性DP

迈不过友情╰ 2021-10-23 16:54 198阅读 0赞

easy 写法。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
    #define LL long long
    #define ULL unsigned LL
    #define fi first
    #define se second
    #define pb push_back
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lch(x) tr[x].son[0]
    #define rch(x) tr[x].son[1]
    #define max3(a,b,c) max(a,max(b,c))
    #define min3(a,b,c) min(a,min(b,c))
    typedef pair<int,int> pll;
    const int inf = 0x3f3f3f3f;
    const int _inf = 0xc0c0c0c0;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    const LL _INF = 0xc0c0c0c0c0c0c0c0;
    const LL mod =  (int)1e9+7;
    const int N = 2e5 + 100;
    int h[N], n, k, m;
    LL pre[N], sum[N];
    LL cost[2][N];
    LL Get(int l, int r){
        return pre[r] - pre[l] - (r-l) * sum[l];
    }
    priority_queue<LL, vector<LL>, greater<LL> > pq;
    void solve(LL pre[], LL now[], int L, int R, int l, int r){
        if(l > r) return ;
        int mid = l+r >> 1;
        now[mid] = _INF;
        int p = L;
        for(int i = min(mid, R); i >= L; --i){
            if(pre[i] - Get(i, mid) > now[mid]){
                now[mid] = pre[i] - Get(i, mid);
                p = i;
            }
        }
        solve(pre, now, L, p, l, mid - 1);
        solve(pre, now, p, R, mid + 1, r);
    }
    int main(){
        int T;
        scanf("%d", &T);
        while(T--){
            scanf("%d%d%d", &n, &k, &m);
            for(int i = 1; i <= n; ++i){
                scanf("%d", &h[i]);
                sum[i] = sum[i-1] + h[i];
                pre[i] = pre[i-1] + sum[i];
                cost[0][i] = -pre[i];
                pq.push(1ll * (n - i + 1) * h[i]);
                if(pq.size() > m) pq.pop();
            }
            int now = 0, pre = 1;
            for(int i = 1; i <= k; ++i){
                swap(now, pre);
                solve(cost[pre], cost[now], 1, n, 1, n);
            }
            LL ans = cost[now][n];
            while(!pq.empty()) {ans += pq.top(); pq.pop();}
            printf("%lld\n", ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/MingSD/p/11298593.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/47d6e5401f1143fa8cad92ed2a257380.png