CF448C [Painting Fence]递归分治

题目链接:http://codeforces.com/problemset/problem/448/C

题目大意:用宽度为1的刷子刷墙,墙是一长条一长条并在一起的。梳子可以一横或一竖一刷到底。求刷完整面墙最少要几次。

关键思路:很有意思,我们会发现,一座墙,从最短的那根往下的矩形区域,全刷完后会形成多座“小山”,这和最先要刷的墙形状是一样的。所以问题就可以进行分治了。

代码如下:

//图像类比
#include<iostream>
#include<algorithm>
using namespace std;
int fence[10000] = { 0 }; int solve(int s, int n) {
int minh = fence[s];
int times = 0;
if (n == 1)return 1;
for (int i = 0; i < n; i++)
fence[s + i] <= minh ? minh = fence[s + i] : minh;
for (int i = 0; i < n; i++)
fence[s + i] -= minh;
times += minh;
int start = 0, end = 0;
for (int i = 0; i <= n; i++) {
if ((fence[s + i] != 0) && (fence[s + i - 1] == 0))start = s + i;
if ((fence[s + i] == 0) && (fence[s + i - 1] != 0)) {
end = s + i - 1;
times += solve(start, end - start + 1);
continue;
}
} return min(times, n);
} int main() {
int Total;
cin >> Total; int i = 0;
for (i = 0; i < Total; i++)
cin >> fence[i]; cout << solve(0, Total)<<endl;
//system("Pause");
return 0; }

  

上一篇:JStorm 是一个分布式实时计算引擎


下一篇:201521123098 《Java程序设计》第13周学习总结