3002 石子归并 3

 时间限制: 1 s

 空间限制: 256000 KB

 题目等级 : 钻石 Diamond

题解

 查看运行结果

题目描述 Description

有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。

输入描述 Input Description

第一行一个整数n(n<=3000)

第二行n个整数w1,w2...wn  (wi <= 3000)

输出描述 Output Description

一个整数表示最小合并代价

样例输入 Sample Input

4

4 1 1 4

样例输出 Sample Output

18

数据范围及提示 Data Size & Hint

数据范围相比“石子归并” 扩大了

分类标签 Tags 点此展开 

动态规划 区间型DP 单调性DP

枚举长度+四边形不等式优化

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define lli long long int 
 7 using namespace std;
 8 const int MAXN=5001;
 9 const int maxn=0x7fffffff;
10 void read(int &n)
11 {
12     char c='+';int x=0;bool flag=0;
13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14     while(c>='0'&&c<='9')
15     x=(x<<1)+(x<<3)+c-48,c=getchar();
16     flag==1?n=-x:n=x;
17 }
18 int n;
19 int a[MAXN]; 
20 int sum[MAXN];
21 int dp[MAXN][MAXN];
22 int mid[MAXN][MAXN];
23 int  main()
24 {
25     read(n);
26     for(int i=1;i<=n;i++)
27         read(a[i]);
28     for(int i=1;i<=n;i++)
29         sum[i]=a[i]+sum[i-1];
30     for(int i=1;i<=n;i++)
31         dp[i][i]=0,mid[i][i]=i;
32     for(int len=1;len<=n-1;len++)
33     {
34         for(int i=1;i<=n-len;i++)
35         {
36             int j=len+i;
37             dp[i][j]=maxn;
38             for(int k=mid[i][j-1];k<=mid[i+1][j];k++)
39             {
40                 if(dp[i][j]>dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
41                 {
42                     dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
43                     mid[i][j]=k;
44                 }
45             }
46         }
47     }
48     
49     printf("%d",dp[1][n]);
50     return 0;
51 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ1563: [NOI2009]诗人小G(决策单调性 前缀和 dp)

    \(f_i = min(f_j + (sum_i - sum_j - 1 - L)^P)\)

    attack
  • P1828 香甜的黄油 Sweet Butter

    题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜...

    attack
  • ZR18提高5解题报告

    设$f[i][j]$表示前$i$个位置,前缀和为$j$的方案数,转移的时候该位置放了什么,以及该位置之前的和是多少。

    attack
  • 数组查询问题-LeetCode 303、304、306

    给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。

    算法工程师之路
  • 洛谷P4768 [NOI2018]归程(Kruskal重构树)

    哎,调了一上午也没调出来,只有72分,可以过所有的单个数据,但是一起跑就GG,而且我本机跑大数据会RE。

    attack
  • Android一 流

    补充Java知识:流 java.io 四个抽象类: 字节流:InputStream OutputStream 字符流:Reader Writer 站在程序角度上...

    小端
  • Tip | 数据类型占位 & 降采样 & 像素读取 & Bitmap & Color源码

    下面修改通道的时候使用的是位运算, 其实对比Color源码我们知道这跟调用Color的API是一样的:

    凌川江雪
  • LOJ#137. 最小瓶颈路 加强版(Kruskal重构树 rmq求LCA)

    attack
  • 洛谷P1137 旅行计划

    题目描述 小明要去一个国家旅游。这个国家有N个城市,编号为1~N,并且有M条道路连接着,小明准备从其中一个城市出发,并只往东走到城市i停止。 所以他就需要选择最...

    attack
  • BZOJ 1179: [Apio2009]Atm(tarjan+SPFA)

    Description Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定, 在每个路口都设立了一个 Siruser i 银行的 AT...

    attack

扫码关注云+社区

领取腾讯云代金券