最美的塔，一个贪心结论＋递推dp，
每次只需讨论当前位对于1的距离与它与它之前的所有的数距离的大小关系或前缀和大小关系
f[0]:=0;
g[0]:=0;
for i:=1 to n do
begin
f[i]:=i-1;
g[i]:=sum[i];
for j:=0 to i-1 do
if ((f[j]+i-j-1<f[i])or(f[j]+i-j-1=f[i])and(sum[i]-sum[j]<g[i]))and(g[j]<=sum[i]-sum[j]) then
begin
g[i]:=sum[i]-sum[j];
f[i]:=f[j]+i-j-1;
end;
end;
f[0]=g[0]=0;
for (int i =1;i <=n;++i)
{
f[i]=i-1; g[i]=sum[i];
for (int j = 0;j<i;++j)
if ((f[j]+i-j-1<f[i] || f[j]+i-j-1==f[i] && sum[i]-sum[j] < g[i])
&& g[j]<=sum[i]-sum[j])
{
g[i] = sum[i] - sum[j];
f[i] = f[j]+i-j-1;
}
}
每次满足条件的差分
（sum前缀和，读入时预处理）
for i:=1 to n do
begin
read(h);
sum[i]:=sum[i-1]+h;
end;
for (int i = 1;i<=n;++i)
{
cin>>h;
sum[i]=sum[i-1]+h;
}
最后得到的结果即递推到的f[n]即是所求解
｛某些方面不够完善，见谅｝
共 1 条回复
我是最强的