http://codeforces.com/problemset/problem/940/E

思路：可以想到划分成k个长度为c的区间得到的答案一定比长度为k*c的区间要好
长度c+a的区间和c，a的区间得到的答案是一样的，这就很明显就是个dp了
dp【i】=min（dp【i-1】+a【i】，dp【i-c】+s【i】-s【i-c】-min（i-c+1~c））；

代码：

#include<bits/stdc++.h>
using namespace std;;
typedef long long ll;
ll a[100010];
ll s[100010];
ll dp[100100];
int m[100100];
set<ll>st;
map<ll,int>mp;
int main()
{

     int n,c;
     scanf("%d %d",&n,&c);
     for(int i=1;i<=n;i++) scanf("%lld",&a[i]),dp[i]=s[i]=s[i-1]+a[i];

     if(c==1) {
        printf("0\n");
        return 0;
     }
     for(int i=1;i<=c;i++){
        st.insert(a[i]);
        mp[a[i]]++;
        m[i]=*st.begin();
     }
     for(int i=c+1;i<=n;i++){
        st.insert(a[i]);
        mp[a[i]]++;
        mp[a[i-c]]--;
        if(mp[a[i-c]]==0) st.erase(a[i-c]);
        m[i]=*st.begin();
     }
     for(int i=c;i<=n;i++){//
        dp[i]=min((dp[i-1]+a[i]),(dp[i-c]+s[i]-s[i-c]-m[i]));
     }

     printf("%lld\n",dp[n]);
}