西安做网站南通公司,外包公司的业务员,炫酷网站源码下载,网站YYQQ建设传送门 题目 cyrcyr今天在种树#xff0c;他在一条直线上挖了n个坑。这n个坑都可以种树#xff0c;但为了保证每一棵树都有充足的养料#xff0c;cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够#xff0c;他至多会种k棵树。假设cyrcyr有某种神能力#xff0c…传送门 题目 cyrcyr今天在种树他在一条直线上挖了n个坑。这n个坑都可以种树但为了保证每一棵树都有充足的养料cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够他至多会种k棵树。假设cyrcyr有某种神能力能预知自己在某个坑种树的获利会是多少可能为负请你帮助他计算出他的最大获利。 输入格式 第一行两个正整数n,k。 第二行n个正整数第i个数表示在直线上从左往右数第i个坑种树的获利。 输出格式 输出1个数表示cyrcyr种树的最大获利。 分析 首先我们先考虑k1的情况则答案即为所有数的最大值。然后我们在考虑k2的情况这是我们有两种选择1.在选择原本的所有数中的最大值ai的同时选一个与它不相邻的数aj2.不选择ai而选择ai-1和ai1。我们推而广之便可以得到这个题的策略每一次选堆中最大的元素将以这个元素为中心的li和ri将会产生的影响放入堆中因为以某点为中心可能不止向两侧扩展一次所以要用lr数组记录我们要注意每次产生的影响是aliari-ai因为这样下一次选这两个点便可以将其上一次扩展的影响覆盖了。注意每一次扩展的lr要打一个标记以防止被以其他点为中心的点二次访问每一次更新lr也要注意将其更新成lli和rri因为某点的左右边界的点也可能扩展过。最后我们要注意如果哪一次堆顶元素为非正数就代表这之后任何扩展都不能给答案带来正效应了直接跳出循环即可。 代码 #includeiostream
#includecstdio
#includecstring
#includestring
#includealgorithm
#includecctype
#includecmath
#includecstdlib
#includequeue
#includectime
#includevector
#includeset
#includemap
#includestack
using namespace std;
#define f first
#define s second
long long a[600000],used[600000],l[600000],r[600000];
priority_queuepairlong long,long long q;
inline void read(long long x){long long f1;x0;char sgetchar();while(s0||s9){if(s-)f-1;sgetchar();}while(s0s9){xx*10(s-0);sgetchar();}x*f;
}
int main()
{ long long n,m,i,j,k;read(n),read(m);for(i1;in;i){read(a[i]);q.push(make_pair(a[i],i));l[i]i-1;r[i]i1;}long long ans0;while(m--){while(used[q.top().s])q.pop();long long xq.top().f,yq.top().s;q.pop();if(x0)break;ansx;a[y]a[l[y]]a[r[y]]-x;used[l[y]]used[r[y]]1;l[y]l[l[y]];r[l[y]]y;r[y]r[r[y]];l[r[y]]y;q.push(make_pair(a[y],y));}printf(%lld\n,ans);return 0;
} 转载于:https://www.cnblogs.com/yzxverygood/p/9135042.html
