poj 2433 Landscaping 贪心 - c++编程基础

很想知道这个题目有没人用dp做的。因为我一开始想到的就是dp，但是没设计出有效的解法。

但是其实这个题目应该还是比较明显的符合贪心的性质的，那么直接贪一下就好了。

#include   
#include   
#include   
using namespace std;  
const int maxn=1e3+9;  
int a[maxn];  
int n,k;  
int work()  
{  
    int ans=1e9,front,end;  
    int flag=1;  
    for(int i=1;i<=n;i++)  
    {  
        if(flag&&a[i]>a[i+1])  
        {  
            int t=flag,s=i;  
            while(t>=1&&a[t]>=a[t-1]) t--;  
            while(s<=n&&a[s]>=a[s+1]) s++;  
            if(t>=1||s<=n)  
            {  
                int sum=0,tmp=max(a[t],a[s]);  
                for(int j=t+1;jtmp)  
                sum+=a[j]-tmp;  
                if(sum




a[i]) flag=i+1;  
    }  
  
    int tmp=max(a[front-1],a[end+1]);  
    for(int j=front;j<=end;j++)  
    if(a[j]>tmp)  
    a[j]=tmp;  
    return ans;  
}  
  
  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    while(scanf("%d %d",&n,&k)!=EOF)  
    {  
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);  
        a[n+1]=0;  
        int sum=0;  
        bool flag=true;  
        for(int i=1;i<=n;i++)  
        {  
            if(flag&&a[i]>a[i+1]) sum++;  
            if(a[i+1]a[i]) flag=true;  
        }  
        int ans=0;  
        for(int i=sum;i>k;i--)  
        ans+=work();  
        cout<