【背景描述】#

一排 N 个数， 第 i 个数是 Ai ， 你要找出 K 个不相邻的数， 使得他们的和最大。 请求出这个最大和。

【输入格式】#

第一行两个整数 N 和 K。 接下来一行 N 个整数， 第 i 个整数表示 Ai 。

【输出格式】#

一行一个整数表示最大和， 请注意答案可能会超过 int 范围

【样例输入】#

3 2
4 5 3

【样例输出】#

7

【数据范围】#

对于 20% 的数据， N, K ≤ 20 。 对于 40% 的数据， N, K ≤ 1000 。 对于 60% 的数据， N, K ≤ 10000 。 对于 100% 的数据， N, K ≤ 100000 ， 1 ≤ Ai ≤ 1000000000。

题解#

贪心，每次用一个堆维护最大值 每次都找最大的和他两边的合并，其实是一个可反悔的贪心

主要边界处理

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <list>

using namespace std;

#define LL long long

struct data
{
    LL Num;
    int pos;
    bool operator<(const data &a) const
    {
        return Num == a.Num ? pos < a.pos : Num > a.Num;
    }
};

set<data> st;

LL a[100005];
int nex[100005], fre[100005];

LL Merge()
{
    int A = st.begin()->pos;
    LL ans = a[A];
    a[A] = -a[A];
    a[A] += a[fre[A]], a[A] += a[nex[A]];
    st.erase(st.begin());
    st.erase((data){a[fre[A]], fre[A]});
    st.erase((data){a[nex[A]], nex[A]});
    st.insert((data){a[A], A});
    if (fre[fre[A]])
        nex[fre[fre[A]]] = A;
    if (nex[nex[A]])
        fre[nex[nex[A]]] = A;
    fre[A] = fre[fre[A]];
    nex[A] = nex[nex[A]];
    return ans;
}
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        fre[i] = i - 1;
        nex[i] = i + 1;
        st.insert((data){a[i], i});
    }
    nex[n] = 0;
    a[0] = 0x8080808080808080ll;
    LL ans = 0;
    while (k--)
    {
        ans += Merge();
    }
    printf("%lld", ans);
}