[DP]Tower

描述

Rainbow和Freda要在Poetic Island市的一座山脚下盖房子定居了……盖房子需要钢材，幸运的是，这里有排成一行的n座废弃的铁塔，从左到右编号为1~n，其中第i座的高度为h[i]。
Rainbow和Freda想盖一座上面小下面大的城堡，并且城堡的层数尽可能多。因此，他们要把这些铁塔分成尽量多组，每组内的铁塔编号必须是连续的，并且从左到右各组内铁塔的高度之和单调不减。
但是Rainbow和Freda简直弱爆了有木有，于是请你帮忙计算一下最多能分成多少组呢？

#include<iostream>
#include<cstdio>
using namespace std;
int n,f[5010];
long long g[5010],a[5010],s[5010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
}
g[1]=s[1]; f[1]=1;
for(int i=2;i<=n;++i)
for(int j=i-1;j>=0;--j)
if(s[i]-s[j]>=g[j])
{
f[i]=f[j]+1;
g[i]=s[i]-s[j];
break;
}
printf("%dn",n-f[n]);
return 0;
}

用f[i]表示到第i个铁塔最多分为多少组，f数组单调不降，用s[i]数组表示前缀和,g[i]表示以第i个塔为最后一组高度和

那么当s[i]-s[j]>=g[j]时f[i]=f[j]+1,因为f单调不降，所以分组的塔的高度和满足时越小越好。

最后

以上就是清脆春天为你收集整理的[DP]Tower的全部内容，希望文章能够帮你解决[DP]Tower所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。