https://codeforces.com/problemset/problem/940/E
题目大意:
给你一个长度n(n<=1e5)的数组a(1<=ai<=1e9)和一个值c([1,1e5])
定义一个子数组[le,ri]的权值大小为sum[le,ri]减去[le,ri]中最小的(ri-le+1)/c个数的和
问将数组分为子数组,使得所有子数组的权值和最小。
分析:
根据这个题意,大家首先想到的就肯定是每个子数组的长度都是c的倍数。
我们冷静点分析
对于长度小于c的,我们怎么优化都没有用了,
对于长度等于c的,不再继续划分就ok
长度大于c小于2c的,我们把它划分为长度为c的一段和其他的可能两端或一段,
`因为一个数组的子数组中的最小值肯定小于它的最小值,
所有这种划分肯定不会变得更糟,但有可能变好
综上,再加上一点分析
在最终的最优解之一中:
肯定有这样一种划分使得它不劣于最优解:
子区间的长度只有两种,1或者c
因为长度小于c的都可以分解成长度为1,也不会变得更糟。
长度大于c的可以分解成若干个c和若干个1。
所以我们用dp[i]表示将[1,i]区间划分得到的最小值
那么dp[i]=min( dp[i-1]+a[i],dp[i-c]+sum[i-c+1,i]-[i-c+1,1]区间的最小值)
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n) for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//输入输出
#define PII pair<int,int>
#define PB push_back
#define x first
#define y second
using namespace std;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
typedef long long ll;
#define stdcpph
#define CPP_IO
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint>
inline void IN(INint &x)
{
x = 0; int f = 1; char c; cin.get(c);
while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
x *= f;
}
template<typename INint>
inline void OUT(INint x)
{
if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(1e5+9);
ll dp[maxn];
int a[maxn];
multiset<int>S;
ll sum(0);
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
int T(1), times(0);
#ifdef CPP_IO// CPP_IO
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//cin >> T;
#else
//IN(T);
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////
while (++times, T--)
{
int n; cin >> n;
int k; cin >> k;
RE2(i, n)
{
cin >> a[i];
S.insert(a[i]); sum += a[i];
if (S.size() > k)
S.erase(S.lower_bound(a[i - k])),sum-=a[i-k];
dp[i] = min(dp[i - 1] + a[i], i-k<0?llinf:dp[i - k] + sum - *S.begin());
}
cout << dp[n] << endl;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
return 0;
}