Codeforces-940E

发表于 | 分类于 | 浏览 次

题解

$dp[i]$表示前i个数字组成的最小答案，得到状态转移方程
$$ dp[i]={min(\\
dp[i-1]+a[i],\\
dp[i-c]+\sum_{j=i-c+1}^{i}a[i]-\min_{j=i-c+1}^{i}a[i]
\\) }
$$
维护动态集合（有不停的添加删除元素）的最小值用muiltset

总结

解题时要想到枚举思路，dp，二分，贪心等常用思路都要考虑到。当确定$dp[i]$的意义后，要大胆的写出方程。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "bits/stdc++.h"
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
#define L index*2
#define R index*2+1
using namespace std;
typedef long long ll;
const ll MAXN=1e6+100;
const ll MOD=1e9+7;
ll arr[MAXN];
ll dp[MAXN];
ll sum[MAXN];
multiset<ll> se;
int main(int argc, char const *argv[]) {
    ll n,c;
    while (cin>>n>>c) {
        se.clear();
        for(int i=1;i<=n;++i)
            scanf("%lld",&arr[i]);
        sum[0]=0;
        for(int i=1;i<=n;++i)
            sum[i]=sum[i-1]+arr[i];
        dp[0]=0;
        for(int i=1;i<c;++i)
        {
            dp[i]=dp[i-1]+arr[i];
            se.insert(arr[i]);
        }
        for(int i=c;i<=n;++i)
        {
            se.insert(arr[i]);
            dp[i]=min(dp[i-1]+arr[i],dp[i-c]+sum[i]-sum[i-c]-*(se.begin()));
            se.erase(se.find(arr[i-c+1]));
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}