CF940E Cashback

CF940E Cashback

Description

链接

Solution

注意到分成C+1一定没有分成C更优

于是每个状态只有两种转移策略

线段树优化一下即可

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    int f = 1 ,x = 0;
    char ch;
    do
    {
        ch = getchar();
        if(ch == '-') f = -1;
    }while(ch < '0'||ch > '9');
    do
    {
        x = (x<<3) + (x<<1) + ch - '0';
        ch = getchar();
    }while(ch >= '0'&&ch <= '9');
    return f*x;
}

const int MAXN = 100000 + 10;

int n;
int a[MAXN];
int c;

#define lc o<<1
#define rc o<<1|1

int T[MAXN<<2];

inline void build(int o,int l,int r)
{
    T[o] = 1<<30;
    if(l == r) 
    {
        T[o] = a[l];
        return;
    }
    int mid = (l + r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    T[o] = min(T[lc],T[rc]);
    return; 
} 

inline int query(int o,int l,int r,int ql,int qr)
{    
    int mid = (l + r) >> 1;
    if(ql<=l&&r<=qr) return T[o];
    if(l>qr||r<ql) return 1<<30;
    return min(query(lc,l,mid,ql,qr),query(rc,mid+1,r,ql,qr)); 
}

long long dp[MAXN];
long long sum[MAXN];

int main()
{
    n = read();c = read();
    if(!c)
    {
        cout << 0 << endl;
        return 0;
    }
    dp[0] = 0;
    for(int i=1;i<=n;i++) dp[i] = 1LL<<60;
    for(int i=1;i<=n;i++) a[i] = read(),sum[i] = sum[i-1] + a[i];
    build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        dp[i] = min(dp[i],dp[i-1] + a[i]);
        if(i >= c)
        dp[i] = min(dp[i] , dp[i-c] + sum[i] - sum[i-c] - query(1,1,n,i-c+1,i));    
    }  
    cout << dp[n] << endl;
}