解题思路:
这道题开始以为是dp,后来发现如果这样做就会炸空间啊!
于是采用贪心。思路非常神奇。
就是以在每个坑种树的收益建一个大根堆
然后用链表存它的前驱后继(n的后继为1,1的前驱为n)
每次取最大的收益。
那么问题来了————有可能在这个点种树比在它两边各种一棵树收益小。
但一定是两边各种一棵,因为我们建的是大根堆,先出来的一定大。
所以我们可以选这个坑种树,也可以选两边的坑各种一棵,所以我们给我们的贪心一个反悔的机会
就是选在这个坑种树以后将它两边的坑合并为一个价值为(w[l]+w[r]-w[now])的坑,代替我们选择的坑
这里非常的巧妙,就是如果选了这个坑就相当于不在那个中间的坑种树了,而是在它两边各种一棵。
然后放一下丑陋的代码
注意事项:
参考代码:
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> # define M (200000+50) using namespace std; struct node{ int value,place; friend bool operator < (node x,node y) { return x.value < y.value; } }; priority_queue<node> q; int n,m,Ans,chose,nxt[M],pre[M],w[M],l,r; bool vis[M];void change(int x){ vis[x]=1; nxt[pre[x]]=nxt[x]; pre[nxt[x]]=pre[x]; nxt[x]=0; pre[x]=0; }int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&w[i]); } if((n>>1)<m){ cout<<"Error!"<<endl; return 0; } for(int i=1;i<n;i++) nxt[i]=i+1; nxt[n]=1; for(int i=2;i<=n;i++) pre[i]=i-1; pre[1]=n; for(int i=1;i<=n;i++) q.push((node){w[i],i}); for(int i=1;i<=m;i++) { while(vis[q.top().place]) q.pop() ; node temp = q.top(); q.pop(); Ans+= temp.value; l=pre[temp.place]; r=nxt[temp.place]; w[temp.place]=w[l]+w[r]-w[temp.place]; change(l); change(r); q.push((node){w[temp.place],temp.place}); } printf("%d\n",Ans); return 0; }
0.0分
4 人评分
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:653 |
printf基础练习2 (有点不明白)浏览:836 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:535 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:574 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:603 |
求圆的面积 (C语言代码)浏览:1667 |
a+b浏览:432 |
P1000 (C语言代码)浏览:868 |
1054题解浏览:460 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:579 |