题意：城市中有从左到右排列起来的高度为hi的n个塔。现在要求作出一些改变使得景观更美丽，也就是要从左到右排列起来的塔呈非递减序列。你可以用吊车吊起一座塔然后叠加到左右相邻的任意一座塔上，这样新塔的高度等于两座塔之和，每次做这样的操作，塔的总数都会减少1（废话）。问最少进行几次这样子的操作可以使得景观美丽。
dp(i)表示使得前i个塔美丽的最小操作次数，sum(i)表示前i座塔的前缀和，last(i)表示使得前i个塔美丽操作次数最小的情况下，最右侧一座塔最小的塔高。
那么就有状态转移方程:dp(i)=min{dp(j)+i-j+1},sum(i)-sum(j)>=last(j).
1 #include <cstdio> 2 int dp[5010],sum[5010],last[5010]; 3 int main() 4 { 5 int n; 6 scanf("%d",&n); 7 for(int i = 1;i <= n;i++){ 8 int a; 9 scanf("%d",&a); 10 sum[i] = sum[i-1]+a; 11 dp[i] = last[i] = 1<<30; 12 } 13 for(int i = 1;i <= n;i++){ 14 for(int j = 0;j < i;j++){ 15 if(sum[i]-sum[j] >= last[j] && dp[i] >= dp[j]+i-j-1){ 16 dp[i] = dp[j]+i-j-1; 17 if(last[i] > sum[i]-sum[j]) last[i] = sum[i]-sum[j]; 18 } 19 } 20 } 21 printf("%d ",dp[n]); 22 return 0; 23 }