[DBSDFZOJ 多校联训] 就

就

背景描述

一排 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。

第一眼看以为是个思博 $DP$ , 然后发现数据范围 $1 imes 10^{5}$ ...一股子 $O(nlog(n))$ 的味道...

一脸懵逼.png

然后就开始各种瞎**优化然后转背包然后就变成了 $60\%$ 的 $O(n^2)$ 算法.

正解果然特么是个贪心.

首先把所有的点都怼进一棵平衡树, 以权值降序第一关键字, 下标升序为第二关键字排序. 然后建立一个链表保存左侧第一个存在结点与右侧第一个存在结点的下标.

然后每次取值最大的元素, 将它和它左右的结点的数据从平衡树中删除, 再把对应的数据改成它的左侧结点与右侧结点的和减去它本身(为了保留不再选取该结点而改选两侧结点的可能性与结果的正确性). 然后修改联保中保存的左侧第二个与右侧第二个元素的右侧/左侧结点下标.

一直贪心 $k$ 次即可得解.总时间复杂度约为 $O(nlog(n))$

参考代码:

GitHub

 1 #include <set>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <iostream>
 6 #include <algorithm>
 7 
 8 #define int long long
 9 const int MAXN=1000010;
10 const long long INF=0x3FFFFFFFFFFFFFFF;
11 
12 struct Node{
13     long long value;
14     int pos;
15     Node(long long value=0,int pos=0){
16         this->value=value;
17         this->pos=pos;
18     }
19     bool friend operator <(const Node &tmp,const Node &y){
20         return tmp.value!=y.value?tmp.value>y.value:tmp.pos<y.pos;
21     }
22 };
23 
24 int n;
25 int k;
26 long long ans;
27 int next[MAXN];
28 int front[MAXN];
29 std::set<Node> s;
30 long long data[MAXN];
31 
32 void Initialize();
33 void Delete(int);
34 
35 signed main(){
36     Initialize();
37     while(k--){
38         int tmp=s.begin()->pos;
39         ans+=data[tmp];
40         data[tmp]=data[front[tmp]]+data[next[tmp]]-data[tmp];
41         s.erase(s.begin());
42         s.erase(Node(data[front[tmp]],front[tmp]));
43         s.erase(Node(data[next[tmp]],next[tmp]));
44         s.insert(Node(data[tmp],tmp));
45         Delete(tmp);
46     }
47     printf("%lld
",ans);
48     return 0;
49 }
50 
51 void Delete(int tmp){
52     if(front[front[tmp]]){
53         next[front[front[tmp]]]=tmp;
54     }
55     if(next[next[tmp]]){
56         front[next[next[tmp]]]=tmp;
57     }
58     front[tmp]=front[front[tmp]];
59     next[tmp]=next[next[tmp]];
60 }
61 
62 void Initialize(){
63     scanf("%lld%lld",&n,&k);
64     for(int i=1;i<=n;i++){
65         scanf("%lld",data+i);
66         front[i]=i-1;
67         next[i]=i+1;
68         s.insert(Node(data[i],i));
69     }
70     data[0]=-INF;
71     next[n]=0;
72 }

Backup

以及日常图包