bzoj 1200: [HNOI2005]木梳 DP

时间:2024-10-12 11:33:49

1200: [HNOI2005]木梳

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

Description

bzoj 1200: [HNOI2005]木梳 DP

bzoj 1200: [HNOI2005]木梳 DP

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
bzoj 1200: [HNOI2005]木梳 DP
  一般的贪心策略还是需要较严格的证明的。比如这道题,位置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);
}