栅栏涂漆测评
题目描述
zed 最近总是受到 Farmer 的困扰,因此他在自家的门前插了一排栅栏以防农气的入侵。栅栏由 N 个竖条栅栏横向组成,每个竖条栅栏宽度为 1。过了一段时间,zed 觉得栅栏非常不美观。因此,他想给栅栏涂上颜色。问题是,zed的刷子宽度只有 1,也就是说,一次只能将连续的一排或一列格子涂上颜色(长度任意)。zed 想用最少的次数把栅栏全部涂上颜色(注意,一个格子不能重复涂色)。但是 zed 现在要去刷 DP 神题,没时间,所以这个问题就交给你了。
输入
第一行为一个整数 N,代表栅栏的宽度。
第二行为 N 个整数 h 1 ~ h n ,代表从左向右每个竖条栅栏的高度。
输出
输出文件有且仅有一行,一个整数 ans,代表将整个栅栏涂色所用最少次数。
样例输入输出
color.in
5
2 1 2 2 1color.out
3
color.in
2
2 2
color.out
2
数据约定
1~3 N≤10,1≤h i ≤10 9
4~10 N≤5000,1≤h i ≤3*10 9(不得不说出题人很坑,写的10 9,结果date里面出现了2*10 9多的数......)
反思
其实这题吧,我的想法是特别暴力的,而且我并不知道我的想法是否正确,我们用单调栈来储存,找到一定高度所能达到的最大横最大面积,然后比较,我们是选择横着刷或竖着刷,虽然我的程序有问题,但是还有40pts我也很蒙啊......而且我的代码为什么永远那么长,自己一定要多练一练啊!!!!!
题解
恩......
这题是个分治题
具体思路的话就是下面的了:
我们对这些栅栏,考虑使用横着刷还是竖着刷,首先我们在大区间里面考虑,然后随着横着刷,我们的大区间就会被分割成一个一个的小区间,同样的,我们对小区间也采取这种方式,最后在竖的和横的里面取一个min,最后求出答案就可以啦,注意点是我们递归传递的区间是很有考量的,虽然我到现在也不知道为什么,所以如果有人来看我博客,并且有人知道的话,教一教我啦,O(∩_∩)O谢谢
1 #include<bits/stdc++.h>
2 #define FOR(i,a,b) for(register int i=a;i<=b;i++)
3 #define ROF(i,a,b) for(register int i=a;i>=b;i--)
4 #define ll long long
5 using namespace std;
6 ll n;
7 ll a[5010];
8 const ll N=0x7fffffffff;
9 ll solve(ll l,ll r,ll h)
10 {
11 if(l==r) return 1;
12 ll minh=N;ll ans=0;
13 FOR(i,l,r) if(a[i]<minh) minh=a[i];//由于是递归下来的,所以我们不用
14 //担心h会比minh小.....
15 ans+=minh-h;
16 // cout<<"ans="<<ans<<endl;
17 FOR(i,l,r)
18 {
19 if(a[i]==minh) continue;
20 FOR(j,i,r)
21 {
22 if(a[j+1]==minh||j==r)
23 {
24 ans+=solve(i,j,minh);
25 i=j+1;
26 break;
27 }
28 }
29 }
30 return min(ans,r-l+1);
31 }
32 ll scan()
33 {
34 ll as=0;
35 char c=getchar();
36 while(c<'0'||c>'9') c=getchar();
37 while(c>='0'&&c<='9')
38 {
39 as=(as<<3)+(as<<1)+c-'0';
40 c=getchar();
41 }
42 return as;
43 }
44 int main()
45 {
46 n=scan();int num=0;
47 // cout<<"YY"<<endl;
48 FOR(i,1,n)
49 a[i]=scan();
50
51 cout<<solve(1,n,0);
52 return 0;
53 }
54 /*
55 抠几个细节
56 首先为了避免找到相同的,我们要从断点的下一个开始寻找,这是一点,然后我们就把这个放到下一个里面去循环
代码在这里