[原创]哈理工hrbust OJ 2225 解题报告 【递推】

2015-12-22 10:43:46 Tabris_ 阅读数：782

博客爬取于2020-06-14 22:45:16
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50378327

粉刷栅栏

Time Limit: 500 MS

Memory Limit: 32768 K

Total Submit: 58 (19 users)

Total Accepted: 14 (10 users)

Rating:


Special Judge: No

Description

给定一组长度为 n 的栅栏，从左到右高度依次是 h[i] 。

你需要对这个栅栏粉刷油漆，每次你可以粉刷一行或者一列。

问最少粉刷几次，可以给所有栅栏上漆。（不能多刷）

Input

第一行包含一个整数，表示栅栏的长度。

接下来的一行，包含 n 个数（ n <= 5000 ），依次表示 h[i](0 <= h[i] <= 10) 。

Output

输出一行表示对应的答案。

Sample Input

5

2 2 1 2 1

Sample Output

3

Hint

![](http://acm.hrbust.edu.cn/contests/attached/image/20141231/20141231155623_9
1685.jpg)

其实本题很好想  做不出来 还是想的太多  就一层一层的刷  刷完这层下层分开了 那就当成新的两个栅栏刷就好了  之后接着再刷
看到这里你可能会想到会用到递归  没错！！  本题就是一个递归的思想解决

如果你每次都分出新的栅栏  就会发现每一层其实只有横着和竖着刷两种刷法  两种刷法的话就很好了  只要计算出横着刷用多少下就好了
当然要和竖着刷的次数比较一下  选择小的记录   竖着刷就是有机列就刷几下么

本题复杂的操作就是判断新的多个栅栏的时候   如何更新

首先把每一个栅栏都有的几层都刷上  然后减去  因为刷完了 就相当于没有这几行  之后在遍历一下 看一看那一段还有栅栏需要刷  在重复之前的操作就好了

用递归 ！！

//===================================附代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream> //-递归思想  把每一层分块的部分块的都刷上
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
long long s[5030];
long long solve(long long l, long long r) //刷的时候没有竖着的 都是横着刷的
{
    long long minn = inf, maxn = -1, tem = 0;
    for (long long i = l; i < r; i++)
          //把每行最底下都有的几行给 刷了
            if (minn > s[i]) minn = s[i];
    for (long long i = l; i < r; i++)
        s[i] -= minn;
      //刷完的剪去
        tem += minn;
    for (long long i = l; i < r; i++)
    {
        if (s[i] > 0)
        {
            for (long long j = i; j < r; j++) //把每行断开的给刷了 并且 记录刷的次数
            {
                if (s[j] == 0 || j == r - 1 && s[j] != 0) //判断刷的边界
                {
                    if (j == r - 1 && s[j] != 0)
                          //此情况下 要处理的话应该使左右大一个
                            j++;
                    long long now = solve(i, j);
                                                //横着刷上部分的
                        tem += min(now, j - i); //比较一下横着刷有多少下 竖着刷有多少下  哪个小  就加上哪个
                    i = j;
                    break;
                }
            }
        }
    }
    return tem;
}
int main()
{
    long long n;
    while (scanf("%lld", &n) != EOF)
    {
        for (long long i = 0; i < n; i++)
            scanf("%lld", &s[i]);
        long long res = solve(0, n);
        res = min(res, n);
          //比较一下横着刷有多少下 竖着刷有多少下  哪个小  就输出哪个
            printf("%lld\n", res);
    }
}