1200: [HNOI2005]木梳
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 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 0x3f3f3f3f3f3f3f3fLL
typedef 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);
}
转载于:https://www.cnblogs.com/mhy12345/p/4129603.html
