2020牛客寒假算法基础集训营2_H 施魔法（dp）

题目大意

题目链接

有n个元素（1-n）， 第i个元素能量值为ai， 可以选择至少k的元素施法， 消耗为选择的k个元素所组成的极值的差，每个元素当且仅当被用1次的最小消耗，

分析

首先排序。

f[i] 表示使用前i（包括第i）个元素的最小消耗

然后维护min(f[j - 1] - a[j]) 即可。

代码

/*
power by Solo_Dance
*/
#include <bits/stdc++.h>

#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 3e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

inline ll read() {
    ll res = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = 1;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        res = (res << 3) + (res << 1) + ch - '0';
        ch = getchar();
    }
    return f ? (~res + 1) : res;
}

ll f[N], a[N];

int main() {
    int n = read(), k = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    sort(a + 1, a + 1 + n);
    ms(f, 0);
    for (int i = 1; i < k; ++i) f[i] = INF;
    ll tmp = INF;
    for (int i = k; i <= n; ++i) {
        tmp = min(tmp, f[i - k] - a[i - k + 1]);
        f[i] = tmp + a[i];
    }
    cout << f[n] << "\n";
    return 0;
}

恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。