通过分析发现要得到b序列，只需把a中 ai>a(i+1)&&ai>a(i-1) 和 ai<a(i+1)&&ai<a(i-1),两种情况时，把ai改造一下就可以了，贴代码。。。。。


#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int n,a[100],b[100];
void init()
{
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    b[0]=a[0];
    for(i=1;i<n-1;i++)
    {
        if(a[i]>b[i-1]&&a[i]>a[i+1])
        {
            b[i]=max(b[i-1],a[i+1]);
            continue;
        }
        if(a[i]<b[i-1]&&a[i]<a[i+1])
        {
            b[i]=min(b[i-1],a[i+1]);
            continue;
        }
        b[i]=a[i];
    }
    b[n-1]=a[n-1];
    int ans=0;
    for(i=1;i<n;i++) ans+=fabs(a[i]-b[i])+fabs(b[i]-b[i-1]);
    cout<<ans<<endl;
}
int main()
{
//    freopen("in.txt","r",stdin);
    init();
//    cout << "Hello world!" << endl;
    return 0;
}

• Re:【挺好的一道小贪心】分析 (4) liuzhuo 2012-08-30 21:48:40