首页 > 代码库 > bzoj 1200: [HNOI2005]木梳 DP

bzoj 1200: [HNOI2005]木梳 DP

2024-08-05 02:23:17   221人阅读

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

3
 
 
 
　　一般的贪心策略还是需要较严格的证明的。比如这道题，位置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 0x3f3f3f3f3f3f3f3fLLtypedef long long qword;int h[MAXN];int pp[MAXN][32];;qword dp[MAXN][2][32];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=0;        scanf("%d",&n);        for (i=1;i<=n;i++)        {                scanf("%d",h+i);                sum+=h[i];                for (j=h[i]-1;j<=h[i]+1;j++)                {                        pp[i][++pp[i][0]]=j;                        if (i-1>=1)pp[i-1][++pp[i-1][0]]=j;                        if (i+1<=n)pp[i+1][++pp[i+1][0]]=j;                        if (i-2>=1)pp[i-2][++pp[i-2][0]]=j;                        if (i+2<=n)pp[i+2][++pp[i+2][0]]=j;                }        }        for (i=1;i<=n;i++)        {                sort(pp[i]+1,pp[i]+pp[i][0]+1);                pp[i][0]=unique(&pp[i][1],&pp[i][pp[i][0]+1])-pp[i]-1;                for (j=pp[i][0]+1;j<12;j++)pp[i][j]=0;                while (pp[i][0] && pp[i][pp[i][0]]>h[i])pp[i][pp[i][0]--]=0;        }        for (i=0;i<=n+1;i++)                for (j=0;j<2;j++)                        for (k=0;k<32;k++)                                dp[i][j][k]=-INFL;        for (i=1;i<=pp[1][0];i++)                dp[1][0][i]=dp[1][1][i]=pp[1][i];        for (i=2;i<=n;i++)        {                for (j=1;j<=pp[i-1][0];j++)                {                        for (k=1;k<=pp[i][0];k++)                        {                                if (pp[i-1][j]<pp[i][k])                                {                                        deal(dp[i][0][k],dp[i-1][1][j]+pp[i][k]);                                }else if (pp[i-1][j]>pp[i][k])                                {                                        deal(dp[i][1][k],dp[i-1][0][j]+pp[i][k]);                                }else                                {                                        deal(dp[i][0][k],dp[i-1][0][j]+pp[i][k]);                                        deal(dp[i][1][k],dp[i-1][1][j]+pp[i][k]);                                }                        }                }        }        qword ans=-INFL;        for (i=1;i<=pp[n][0];i++)        {                ans=max(ans,dp[n][0][i]);                ans=max(ans,dp[n][1][i]);        }        printf("%lld",sum-ans);}

 

bzoj 1200: [HNOI2005]木梳 DP


联系
我们