Description
zed 最近总是受到 Farmer 的困扰,因此他在自家的门前插了一排栅栏以防农气的入侵。栅栏由 N 个竖条栅栏横向组成,每个竖条栅栏宽度为 1。
过了一段时间,zed 觉得栅栏非常不美观。因此,他想给栅栏涂上颜色。问题是,zed的刷子宽度只有 1,也就是说,一次只能将连续的一排或一列格子涂上颜色(长度任意)。
zed 想用最少的次数把栅栏全部涂上颜色(注意,一个格子不能重复涂色)。但是 zed 现在没时间,所以这个问题就交给你了。Input
第一行为一个整数 N,代表栅栏的宽度。
第二行为 N 个整数 h 1 ~ h n ,代表从左向右每个竖条栅栏的高度。Output
输出文件有且仅有一行,一个整数 ans,代表将整个栅栏涂色所用最少次数。
Solution:
" 考虑横着涂一次的情况,那么有两个显而易见的事实。
1、 这次涂色长度必须尽可能大。
2、 在这次涂色区域的下方,必定都是横着涂的。
所以,对于一串栅栏h1,h2,...,hn,如果要横着涂,就必定要从底向上涂min{h1,h2,...,hn}次。这样以后,h1,h2,...,hn就会分成若干不连通的子局面。
那么显然可以设计一个分治的算法,时间复杂度为O(N2):
令Solve(l, r, h)代表[l, r]这段栅栏,已经从下向上涂了h格的答案。
令 h′=min{h1,h2,...,hn},那么:
Solve(l,r,h)=min{r−l+1,∑solve(u,v, h ′ )|[u, v]为分割出的子局面}
边界情况:l=r时,答案显然为1。 "
CODE:
#include<iostream>
#include<cstdio>
#define R register
#define go(i,a,b) for(R int i=a;i<=b;i++)
#define M 5000+1
#define inf 2100000000
using namespace std;
int read()
{
int x=,y=;;char c=getchar();
while(c<''||c>'') {if(c=='-') y=-;c=getchar();}
while(c>=''&&c<='') {x=(x<<)+(x<<)+c-'';c=getchar();}
return x*y;
}
int n,h[M];
int solve(int l,int r,int h1)
{
if(l>r) return ;
int minh=inf,ans,l1=l;
go(i,l,r) minh=min(minh,h[i]);
ans=minh-h1;
go(i,l,r)
if(h[i]==minh) ans+=solve(l1,i-,minh),l1=i+;
ans+=solve(l1,r,minh);
return min(ans,r-l+);
}
int main()
{
n=read();go(i,,n) h[i]=read();
printf("%d",solve(,n,));
return ;
}