Codevs 3002 石子归并 3(DP四边形不等式优化)
2024-08-23 04:05:52
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
/*
DP四边形不等式优化.
可证得k取[s[i][j-1],s[i+1][j]]
然后n^2搞就好.
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 3001
using namespace std;
int n,m,f[MAXN][MAXN],s[MAXN][MAXN],w[MAXN];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void slove()
{
for(int i=1;i<=n;i++) s[i][i]=i;
f[0][0]=0;
for(int l=1;l<=n-1;l++)
for(int i=1;i<=n-l;i++)
{
int j=i+l;
for(int k=s[i][j-1];k<=s[i+1][j];k++)
{
if(f[i][j]>f[i][k]+f[k+1][j]+w[j]-w[i-1])
{
f[i][j]=f[i][k]+f[k+1][j]+w[j]-w[i-1];
s[i][j]=k;
}
}
}
}
int main()
{
int x;
memset(f,127/3,sizeof f);
n=read();
for(int i=1;i<=n;i++) x=read(),w[i]=w[i-1]+x,f[i][i]=0;
slove();
printf("%d",f[1][n]);
return 0;
}
最新文章
- AVA数据库连接池.
- 【iCore3 双核心板_FPGA】例程八:触发器实验——触发器的使用
- C语言 内存四大存储区域
- JSP学习——原理
- Heilmeier&#39;s criteria
- Javascript -- toFixed()函数
- Git CMD - status: Show the working tree status
- 错误:[将截断字符串或二进制数据。\r\n语句已终止。]
- POJ 2250(最长公共子序列 变形)
- Mac OSX操作系统安装和配置Zend Server 6教程(3)
- Openjudge-计算概论(A)-求分数序列和
- java并发包分析之———AQS框架
- [物理学与PDEs]第1章第5节 Maxwell 方程组的数学结构, 电磁场的波动性 5.3 电磁场的波动性, 自由电磁波
- mysql中count的注意事项
- day057 基于对象和基于双下划线的多表查询
- underscore.js源码解析【&#39;_&#39;对象定义及内部函数】
- c# datetime用法总结
- Tomcat *的安装和运行(绿色版和安装版都适用)
- js if和switch,==和===
- 【BZOJ 2306】 2306: [Ctsc2011]幸福路径 (倍增floyd)
热门文章
- Failed to transfer file: http://repo.maven.apache.org/maven2/xpp3/xpp3_min/1.1.4c/xpp3_min-1.1.4c.jar
- 【CF1095F】 Make It Connected(最小生成树)
- 浅谈dubbo服务
- 页面 ajax
- Java 之 函数式编程
- vue环境搭建及创建项目
- 解决mysql跟php不在同一台机器上,编译安装php服务报错问题:configure: error: Cannot find MySQL header files under /application/mysql.
- p3.BTC-协议
- 虚拟机NAS存储的安装
- python爬虫爬取get请求的页面数据代码样例