铁塔 题解

题目描述

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

输入输出格式

输入格式：

第一行一个整数 n。 第二行 n 个整数，第 i 个整数表示 h[i]。

输出格式：

输出一个整数，表示(n - 最多能分成的组数)。

题解

　　考试的时候一看就觉得是到贪心，十几分钟就码完了，后来完了，想了想发现自己凉了。如果我们贪心的话，贪心策略就应该是尽可能的少拿前面的。举组反例吧，对于2 2 1 3 3，对于贪心就会这样选择(2) (2) (1 3) 3最后输出3，而最优解却应该是(2) (2 1) (3) (3)最后答案是4。

　　所以我们就只能考虑用动态规划了。

　　状态：f[i]表示前 i 个铁塔最多组成多少组。

　　　　　last[i]前 i 个铁塔的最优解下，最后一组铁塔的数量。

　　转移 ：我们求一个前缀和sum[i]表示前i 个铁塔的高度和，我们可以利用贪心的思想得到当f[i]尽量大时，last[i]会越来越小

　　　　　

代码

 #include <bits/stdc++.h>
 using namespace std;
 const int MAX = 5005;
 long long f[MAX], sum[MAX], last[MAX], a[MAX];
 int main()
 {
     //freopen("tower.in", "r", stdin);
     //freopen("tower.out", "w", stdout);
     int n;
     scanf("%d", &n);
     for(int i = 1; i <= n; ++ i)
     {
         scanf("%lld", &a[i]);
         sum[i] = sum[i - 1] + a[i];
     }
     f[0] = 0;
     for(int i = 1; i <=n; ++ i)
         for(int j = 0; j < i; ++ j)
             if(sum[i] - sum[j] >= last[j])
             {
                 f[i] = f[j] + 1;
                 last[i] = sum[i] - sum[j];
             }
     printf("%lld
", n - f[n]);
 }