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[];

int main()

{

    int n;

    long long ans = ;

    scanf("%d", &n);

    for(int i = ; i <= n; ++i) scanf("%d", &a[i]);

    for(int i = ; i <= n; ++i) ans += max(a[i], a[i - ]);

    printf("%lld\n", ans);

    return ;

}

巴特西

bzoj1345

最新文章

热门文章