洛谷 P1484 种树

题目传送门

解题思路:

本题说每选一个坑,它的左右两个坑都不能选了,可是我们没有办法确定我们选某个坑一定是最优解,怎么办呢?

我们设置一个反悔机制,每当选一个坑,就新设置一个点,使这个点的值为这个坑两边的和减去当前坑的差.

为什么这样做是对的呢?

感性想一下,如果再后面的选坑过程中,我们选到了这个新设置的点,说明我们选上文的那个坑不是最优解,而它的两边更优,那么答案加上新设置的点的值,其实就等价于选那个坑的两边.

我们将所有值扔进一个大根堆中,一直选,直到堆顶为负数,或选够了k个坑为止.

当然了,我们每选一个坑就用一个bool变量标记它的左右两个坑不可选.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 
 7 using namespace std;
 8 
 9 int n,k,l[500002],r[500002];
10 long long ans,c[500002];
11 bool p[500002];
12 struct kkk {
13     long long v,id;
14     bool operator < (const kkk &o) const {
15         return v < o.v;
16     }
17 }e[500002];
18 priority_queue<kkk> a;
19 
20 int main() {
21     memset(p,1,sizeof(p));
22     scanf("%d%d",&n,&k);
23     for(int i = 1;i <= n; i++) {
24         scanf("%lld",&e[i].v);
25         e[i].id = i;
26         l[i] = i - 1;
27         r[i] = i + 1;
28         a.push(e[i]);
29         c[i] = e[i].v;
30     }
31     r[0] = 1;
32     l[n] = n + 1;
33     for(int i = 1;i <= k; i++) {
34         if(a.top().v < 0) break;
35         if(!p[a.top().id]) {
36             i--;
37             a.pop();
38             continue;
39         }
40         kkk t;
41         t = a.top();
42         a.pop();
43         ans += t.v;
44         p[l[t.id]] = p[r[t.id]] = 0;
45         c[t.id] = 0 - c[t.id] + c[l[t.id]] + c[r[t.id]];
46         t.v = c[t.id];
47         l[t.id] = l[l[t.id]];
48         r[t.id] = r[r[t.id]];
49         l[r[t.id]] = t.id;
50         r[l[t.id]] = t.id;
51         a.push(t);
52     }
53     printf("%lld",ans);
54     
55     return 0;
56 }