Codeforces 229D-白红宇的个人博客

Codeforces 229D

发布日期：2021-08-16 08:21:48 浏览次数：1 分类：技术文章

本文共 1058 字，大约阅读时间需要 3 分钟。

一题意描述：

有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 
     
       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
      
       =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 }

转载于:https://www.cnblogs.com/khbcsu/p/3858122.html

转载地址：https://blog.csdn.net/weixin_30794499/article/details/95260609 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：5.14 js对象函数 js操作document对象

下一篇：双内核问题

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章