题意：给你n条1个宽度ai长度的木条，有一个刷子可以一次刷宽度为1长度无限，问你用最少的次数把所有木条都刷满。
思路：我们可以用分治的思想来做，首先找到n条木条最短的木条i，然后减去它的值，再查找，1到i-1，和i+1到n的最小值，由于可以竖着刷，因此要比较
刷完这段区间的横着刷和竖着刷的最小值。最终即为答案。
#include <stdio.h>
#include<string.h>
const int maxn = 5009;
const int inf = 1<<29;
inline int min(int a,int b){return a < b ? a : b;}
int a[maxn];
int DFS(int l,int r)
{
int i,mina = inf;
int sum = 0;
for(i = l;i <= r; i++)
mina = min(mina,a[i]);
for(i = l;i <= r; i++)
a[i] -= mina;
sum = mina;
int ll = l;
for(i = l;i <= r; i++)
{
if(a[i] == 0)
{
sum += DFS(ll,i-1);
ll = i+1;
}
}
if(ll <= r) sum += DFS(ll,r);
return min(sum,r-l+1);
}
int main()
{
int n,i;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%d\n",DFS(0,n-1));
}
return 0;
}
codeforces 448C 搜索,布布扣,bubuko.com
原文：http://www.cnblogs.com/BruceNoOne/p/3900591.html