[BZOJ 2151]种树 题解


题面

$Description$

$A$城市有一个巨大的圆形广场,为了绿化环境和净化空气,市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后,初步规划出$n$个种树的位置,顺时针编号$1$到$n$。并且每个位置都有一个美观度$A_i$,如果在这里种树就可以得到这$A_i$的美观度。但由于$A$城市土壤肥力欠佳,两棵树决不能种在相邻的位置($i$号位置和$i+1$号位置叫相邻位置。值得注意的是$1$号和$n$号也算相邻位置!)。最终市政府给园林部门提供了$m$棵树苗并要求全部种上,请你帮忙设计种树方案使得美观度总和最大。如果无法将$m$棵树苗全部种上,给出无解信息。

$Input$

输入的第一行包含两个正整数n、m。第二行n个整数Ai。

$Output$

输出一个整数,表示最佳植树方案可以得到的美观度。如果无解输出“Error!”,不包含引号。

$Sample Input$

【样例输入1】
7 3
1 2 3 4 5 6 7

【样例输入2】
7 4
1 2 3 4 5 6 7

$Sample Output$

【样例输出1】
15

【样例输出2】
Error!

数据规模

对于全部数据:$m \le n ,-1000 \le A_i \le 1000$
$N$的大小对于不同数据有所不同:

数据编号 $N$的大小 数据编号 $N$的大小
1 30 11 200
2 35 12 2007
3 40 13 2008
4 45 14 2009
5 50 15 2010
6 55 16 2011
7 60 17 2012
8 65 18 199999
9 200 19 199999
10 200 20 200000

思路

本人还是挺菜的,只能写菜鸡算法。正解还是参考了大佬的博客……

首先,如果这道题目没有不能种植在相邻位置的限制,那么答案很显然,把$A_i$按照从大到小排序,取前$m$个数相加即可。

现在题目有了这个限制,我们怎么考虑呢?

首先,假设现在最大的$A_i$是$A_2$,那么我们先把$A_2$取出来,然后把$ans$加上$A_2$,这个时候$A_1$和$A_3$都是不能选了的,那么我们应该把他 骟掉 删掉。可是如果$A_1+A_3 \ge A_2$,你就出锅了。那么我们的解决措施是这样的。我们把$A_1$和$A_3$删掉以后加上一个$A_1+A_3-A_2$的新的美观度。这样,在选了$A_2$以后,如果剩下的里面最大的是$A_1+A_3-A_2$,那么加上这个以后,就等同于选了$A_1+A_3$而没有选择$A_2$。

那么我们考虑这个新的美观度放在哪里。这个新权值的意义是选了$A_1$和$A_3$,也就是说,如果选到了这个,那么$A_n$和$A_4$就不能选了,所以我们把新权值放到$A_n$和$A_4$之间(注意这是一个环!不是4~n的区间,是这个区间的补集!)。用一个更容易理解的例子。如果新放进去的是$A_2+A_4-A_3$,那么显然不能选的是$A_1$和$A_5$,所以新的权值应该放到$A_1$和$A_5$之间。现在比较舒服的事情就是如果原来 骟掉 删掉的是$A_x$,那么我们把新的权值放到$A_x$的位置显然是可行的。这个问题就这么得解了!

然后我们发现,我们这么一搞,就还剩下$N-1$个物品,我们要从中选$M-2$个物品。接下来我们继续像这样取$M-1$次就可以了。

完结!撒花!★,°:.☆( ̄▽ ̄)/$:.°★


算法

把所有的$A$扔进一个大根堆(扔一个 ($A_i$,$i$) 的pair),同时用双向链表连接每个$A_i$。每次取出堆顶元素,设堆顶元素为($A_k$,$k$),然后把$ans$加上$A_k$,在双向链表中把$A_k$的前驱和后继 骟掉 删掉,把$A_k$改成$A_{k-1}+A_{k+1}-A_k$,再扔到堆里。如此做$M$次。输出$ans$即可。


$Code$

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 200005
using namespace std;
int n,m,a[MAXN],ans=0;
int pre[MAXN],nxt[MAXN],vis[MAXN];
priority_queue< pair<int,int>,vector< pair<int,int> > >q;

inline void getnum(int &num)
{
num=0;
int f=1;
register char c=getchar();
while (!isdigit(c))
{
if (c=='-')
f=-1;
c=getchar();
}
while (isdigit(c))
{
num=(num<<3)+(num<<1)+(c&15);
c=getchar();
}
num*=f;
return;
}

inline void init()
{
for (register int i=1;i<=n;++i)
pre[i]=i-1,nxt[i]=i+1;
pre[1]=n;
nxt[n]=1;
for (register int i=1;i<=n;++i)
q.push(make_pair(a[i],i));
return;
}

inline void del(int x)
{
vis[x]=1;
register int l=pre[x],r=nxt[x];
nxt[l]=r,pre[r]=l;
return;
}

int main()
{
getnum(n),getnum(m);
if (m>(n>>1))
{
printf("Error!\n");
return 0;
}
for (register int i=1;i<=n;++i)
getnum(a[i]);
init();
for (register int i=1;i<=m;++i)
{
while (vis[q.top().second])
q.pop();
register int tmp=q.top().second;
q.pop();
ans+=a[tmp];
a[tmp]=a[pre[tmp]]+a[nxt[tmp]]-a[tmp];
del(pre[tmp]);
del(nxt[tmp]);
q.push(make_pair(a[tmp],tmp));
}
printf("%d\n",ans);
return 0;
}

注意点

快读每次都打上负数吧……不会慢多少的。不要老是想着数据范围,有负数再打符号。凭我这愚蠢的大脑肯定是会忘记的……

-------------本文结束,感谢阅读-------------
0%