bzoj 1200: [HNOI2005]木梳 DP

2022-10-09 10:33:47

1200: [HNOI2005]木梳

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 266 Solved: 125
[Submit][Status]

Description

Input

第一行为整数L，其中4<=L<=100000，且有50%的数据满足L<=104，表示木板下侧直线段的长。第二行为L个正整数A1,A2,…,AL，其中1

Output

仅包含一个整数D，表示为使梳子面积最大，需要从木板上挖掉的格子数。

Sample Input

9
4 4 6 5 4 2 3 3 5

Sample Output

　　一般的贪心策略还是需要较严格的证明的。比如这道题，位置pos所处的可能高度应该是h[i]+/-1 (pos-2<=i<=pos+2)稍有疏忽，就会将i的范围搞错。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

using namespace std;

#define MAXN 110000

#define INFL 0x3f3f3f3f3f3f3f3fLL

typedef long long qword;

int h[MAXN];

int pp[MAXN][];;

qword dp[MAXN][][];

inline void deal(qword &x,qword y)

{

        if (x<y)x=y;

}

int main()

{

        freopen("input.txt","r",stdin);

        int i,j,k,k2,x,y,z,n,m;

        qword sum=;

        scanf("%d",&n);

        for (i=;i<=n;i++)

        {

                scanf("%d",h+i);

                sum+=h[i];

                for (j=h[i]-;j<=h[i]+;j++)

                {

                        pp[i][++pp[i][]]=j;

                        if (i->=)pp[i-][++pp[i-][]]=j;

                        if (i+<=n)pp[i+][++pp[i+][]]=j;

                        if (i->=)pp[i-][++pp[i-][]]=j;

                        if (i+<=n)pp[i+][++pp[i+][]]=j;

                }

        }

        for (i=;i<=n;i++)

        {

                sort(pp[i]+,pp[i]+pp[i][]+);

                pp[i][]=unique(&pp[i][],&pp[i][pp[i][]+])-pp[i]-;

                for (j=pp[i][]+;j<;j++)pp[i][j]=;

                while (pp[i][] && pp[i][pp[i][]]>h[i])pp[i][pp[i][]--]=;

        }

        for (i=;i<=n+;i++)

                for (j=;j<;j++)

                        for (k=;k<;k++)

                                dp[i][j][k]=-INFL;

        for (i=;i<=pp[][];i++)

                dp[][][i]=dp[][][i]=pp[][i];

        for (i=;i<=n;i++)

        {

                for (j=;j<=pp[i-][];j++)

                {

                        for (k=;k<=pp[i][];k++)

                        {

                                if (pp[i-][j]<pp[i][k])

                                {

                                        deal(dp[i][][k],dp[i-][][j]+pp[i][k]);

                                }else if (pp[i-][j]>pp[i][k])

                                {

                                        deal(dp[i][][k],dp[i-][][j]+pp[i][k]);

                                }else

                                {

                                        deal(dp[i][][k],dp[i-][][j]+pp[i][k]);

                                        deal(dp[i][][k],dp[i-][][j]+pp[i][k]);

                                }

                        }

                }

        }

        qword ans=-INFL;

        for (i=;i<=pp[n][];i++)

        {

                ans=max(ans,dp[n][][i]);

                ans=max(ans,dp[n][][i]);

        }

        printf("%lld",sum-ans);

}