一 題意描述：

有n(1<=n<=5,000)座塔排在一條直線上，從左到右每個(gè)塔的高度分別為hi(1<=hi<=100,000)，每次操作你可以選擇一座塔（假設(shè)是第i座），用吊車把它吊起來，然后放到與它相鄰的一座塔上（可以是第i-1座也可以是第i+1座），這樣，新塔的高度為兩座塔的和，完成操作后，塔的總數(shù)減少一座。問最少需要多少次操作可以使得所有的塔從左到右形成一個(gè)非遞減序列。

二 思路分析：

設(shè)dp[i]表示使前i座塔呈現(xiàn)非遞減所需要的最小步驟數(shù)目，那么合并[j,i]座塔需要i-j步.

那么我們可以求得dp方程：dp[i]=min{dp[j]+i-j-1 ?| ?j<i,h(j+1)+h(j+2)+·····+h(i)>=last[j]}

三 源碼展示：

1 #include <cstdio> 2 int dp[5010],sum[5010],last[5010]; 3 int main() 4 { 5 int n; 6 scanf("%d",&n); 7 memset(sum,0,sizeof(sum));//把sum首先置為0，然后開始輸入數(shù)據(jù)并逐步累加 8 dp[0]=0;last[0]=0; 9 for(int i = 1;i <= n;i++) 10 { 11 int a; 12 scanf("%d",&a); 13 sum[i]=sum[i-1]+a; 14 dp[i]=last[i]=1<<30;//初始值設(shè)為2的30次方大 15 } 16 for(int i=1;i<=n;i++) 17 { 18 for(int j=0;j<i;j++) 19 { 20 if(sum[i]-sum[j]>=last[j]&&dp[i]>=dp[j]+i-j-1) 21 { 22 dp[i]=dp[j]+i-j-1; 23 if(last(i)>sum[i]-sum[j]) last[i]=sum[i]-sum[j]; 24 } 25 } 26 } 27 printf("%d\n",dp[n]); 28 return 0; 29 }

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

總結(jié)

以上是生活随笔為你收集整理的Codeforces 229D的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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