【51nod1519】拆方块[Codeforces]（dp）

　　题目传送门：1519 拆方块

　　首先，我们可以发现，如果第i堆方块被消除，只有三种情况：

　　1、第i-1堆方块全部被消除；

　　2、第i+1堆方块全部被消除；（因为两侧的方块能够保护这一堆方块在两侧不暴露）

　　3、第i堆方块过了h[i]次操作后，从上到下被消除。

　　于是我们设l[i]为第i堆方块从左边开始消除的最小操作次数，设r[i]从右边开始消除的最小操作次数。

　　然后从左向右dp出l[i]，从右向左dp出r[i]，然后就能算答案了。

　　代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<algorithm>

#include<queue>

#include<vector>

#define ll long long

ll read()

{

    ll tmp=; char f=,c=getchar();

    while(c<''||''<c){if(c=='-')f=-;c=getchar();}

    while(''<=c&&c<=''){tmp=tmp*+c-'';c=getchar();}

    return tmp*f;

}

using namespace std;

int l[],r[],h[];

int main()

{

    int n=read(),i;

    for(i=;i<=n;i++)h[i]=read();

    l[]=; for(i=;i<=n;i++)l[i]=min(l[i-]+,h[i]);

    r[n]=; for(i=n-;i;i--)r[i]=min(r[i+]+,h[i]);

    int ans=min(l[],r[]);

    for(i=;i<=n;i++)ans=max(ans,min(l[i],r[i]));

    printf("%d",ans);

}

巴特西

【51nod1519】拆方块[Codeforces]（dp）

最新文章

热门文章