即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

bzoj1749 [usaco2005 open]Landscaping 地形改造

编程语言 qq_35866453 11℃ 0评论

这题很强势,写了半天炸了,判断山顶一直很懵逼,知道问了Claris才知道原来就是按照题目那样子暴力就好了= =。


找出所有山峰,然后贪心减去代价最小的= =

#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e3+5;
int a[N],tmp;
int n,m,i,j,k,x,y,t,l,r,ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(a[0]=~0U>>1,i=1;i<=n;i++)scanf("%d",&a[i]),a[0]=a[0]0]:a[i];
    for(a[n+1]=a[0],i=1;iwhile (i1])i++;
        while (i=a[i+1])i++; 
    }
    for(m=t-m;m>0;m--)
    {
        for(i=0,tmp=~0U>>1;iwhile (i<=n&&a[i]<=a[i+1])i++;
            while (i<=n&&a[i]>=a[i+1])i++;
            if (a[i]>k)k=a[i];
            for(t=0,x=j;x<=i;x++)if (a[x]>k)t+=a[x]-k;
            if (tfor(ans+=tmp;l<=r;l++)if (a[l]>y)a[l]=y;
    }
    printf("%d\n",ans);

} 

转载请注明:CodingBlog » bzoj1749 [usaco2005 open]Landscaping 地形改造

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情