904E

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

$dp$

凉凉.jpg

看到题就想决策单调性，想了一个多小时也没想出来，排名$200+$,$gg$

事实上，我们只可能每$c$个或每一个分一段,假设我们分了一段长为$c$,如果添加一个新元素，如果新的比老的大，没影响，如果小，那么亏损，所以不如不加

 #include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long ll;

const int N = 1e5 + ;

int n, c;

ll ans;

int Log[N];

ll a[N][], dp[N];

ll rmq(int l, int r) {

    if(l > r) {

        swap(l, r);

    }

    int x = Log[r - l + ];

    return min(a[l][x], a[r - ( << x) + ][x]);

}

int main() {

    scanf("%d%d", &n, &c);

    for(int i = ; i <= n; ++i) {

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

        ans += a[i][];

    }

    for(int i = ; i <= n; ++i) {

        Log[i] = Log[i >> ] + ;

    }

    for(int j = ; j <= ; ++j) {

        for(int i = ; i + ( << j) -  <= n; ++i) {

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

        }

    }

    for(int i = c; i <= n; ++i) {

        dp[i] = max(dp[i - ], dp[i - c] + rmq(i, i - c + ));

    }

    cout << ans - dp[n];

    return ;

}