首页 > 代码库 > 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;
}
View Code

 

bzoj1345