#include<stdio.h> #include<algorithm> using namespace std; int a[5005]; int n; int dfs(int l, int r) { int re = r - l + 1; //水平刷最下那层的 int now = 199999999; for(int i = l; i <= r; i++) { now = min(a[i], now); } for(int i = l; i <= r; i++) { a[i] -= now; } for(int i = l; i <= r; i++) { if(a[i] && !a[i-1]) { int j = i; while(a[j + 1]) j++; now += dfs(i, j); } } //除了水平刷之后其他方法的最小的 return min(re, now); //两者取小值 } int main() { while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } int re = dfs(1, n); printf("%d\n", re); } return 0; }
刷墙问题