首页 > 代码库 > Codeforces 229D
Codeforces 229D
一 题意描述：
有n(1<=n<=5,000)座塔排在一条直线上，从左到右每个塔的高度分别为hi(1<=hi<=100,000)，每次操作你可以选择一座塔（假设是第i座），用吊车把它吊起来，然后放到与它相邻的一座塔上（可以是第i-1座也可以是第i+1座），这样，新塔的高度为两座塔的和，完成操作后，塔的总数减少一座。问最少需要多少次操作可以使得所有的塔从左到右形成一个非递减序列。
二 思路分析：
设dp[i]表示使前i座塔呈现非递减所需要的最小步骤数目，那么合并[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，然后开始输入数据并逐步累加 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;//初始值设为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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。