368 字
2 分钟
就
【背景描述】
一排 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);}