題目鏈接：http://codeforces.com/problemset/problem/448/C

題意：

　　有n個(gè)木板豎著插成一排柵欄，第i塊木板高度為a[i]。

　　你現(xiàn)在要將柵欄上所有地方刷上油漆。

　　每次你可以選擇豎著刷或橫著刷，但必須保證一次刷的地方不能間斷。

　　問你至少要刷幾次才能刷滿。

?

題解：

　　首先有一個(gè)貪心結(jié)論：

　　　　對(duì)于當(dāng)前要刷的一片區(qū)域，令minn為這片區(qū)域的最小高度。

　　　　如果選擇橫著刷，則至少要將區(qū)域底部的minn層刷完。

　　　　如圖，至少要將下面兩層刷完：

　　　　

　　

　　然后考慮如何分治：

　　　　對(duì)于當(dāng)前的這一片區(qū)域，將最下面的minn層去掉之后，原區(qū)域就變成了若干個(gè)小區(qū)域。

　　　　這樣就轉(zhuǎn)化成了若干個(gè)子問題。

　　　　所以當(dāng)前區(qū)域的最小次數(shù) = min( 只豎著刷的次數(shù), 先橫著刷minn次 + ∑ 子區(qū)域的最小次數(shù) )

　　　　即：dfs(x,y) = min(y-x+1, minn + ∑ dfs(Li,Ri))

　　　　邊界條件：x == y時(shí)，最多只用豎著刷一次。

?

AC Code:

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #define MAX_N 5005 5 #define INF 1000000000 6 7 using namespace std; 8 9 int n; 10 int a[MAX_N]; 11 12 int dfs(int x,int y) 13 { 14 if(x==y) return 1; 15 int minn=INF; 16 for(int i=x;i<=y;i++) minn=min(minn,a[i]); 17 for(int i=x;i<=y;i++) a[i]-=minn; 18 int sum=0; 19 int p=x; 20 for(int i=x;i<=y;i++) 21 { 22 if(a[i] && (i==y || !a[i+1])) sum+=dfs(p,i); 23 if(!a[i] && i<y && a[i+1]) p=i+1; 24 } 25 return min(sum+minn,y-x+1); 26 } 27 28 int main() 29 { 30 cin>>n; 31 for(int i=1;i<=n;i++) cin>>a[i]; 32 cout<<dfs(1,n)<<endl; 33 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Leohh/p/8252765.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 448C Painting Fence：分治的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。