首页 > 代码库 > bzoj1345
bzoj1345
贪心
这并没有想清楚就看题解了。。。
看上去肯定是贪心,那么怎么贪呢?事实上,我们想一下,假设max(a[i],a[i+1])中a[i]没有合并,那么后面取max肯定是a[i+1],因为如果后面合并之后比a[i+1]大,那么不如先和a[i]合并了,如果后面合并了比a[i+1]小,那么也没用,因为不可能选到比a[i+1]小的
#include<bits/stdc++.h> using namespace std; int a[1000010]; int main() { int n; long long ans = 0; scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(int i = 2; i <= n; ++i) ans += max(a[i], a[i - 1]); printf("%lld\n", ans); return 0; }
bzoj1345
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。