codevs 1048石子归并
2024-08-21 13:10:39
传送门
1048 石子归并
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。
输入描述 Input Description
第一行一个整数n(n<=100)
第二行n个整数w1,w2...wn (wi <= 100)
输出描述 Output Description
一个整数表示最小合并代价
样例输入 Sample Input
4
4 1 1 4
样例输出 Sample Output
18
【题目大意】合并石子,花费是合并两石子的重量和,求最小。
【思路】动态规划区间型dp 数据在一条链上。记f[i][j]是合并区间i--j的最小代价,那么答案为f[1][n]。
转移方程:f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);sum[i]为前i堆石子重量和,用前缀和优化。
合并i--j最小 ,可是由两堆合并来,i--k 和k+1--j这两堆,那么我们在合并i--j是 i--k与k+1--j已经知道了答案,
所以我们要让内层循环倒着推。枚举中间点k,也可以枚举长度,我更喜欢前者。
【code】
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int w[],f[][],sum[];
int n;
int main() {
scanf("%d",&n);
for(int i=; i<=n; i++) {
scanf("%d",&w[i]);
sum[i]=sum[i-]+w[i];
}
for(int i=; i<=n; i++)
for(int j=i-; j>=; j--) {
f[j][i]=0x3f3f3f3f;
for(int k=j; k<i; k++)
f[j][i]=min(f[j][i],f[j][k]+f[k+][i]+sum[i]-sum[j-]);
} printf("%d\n",f[][n]);
return ;
}
最新文章
- [SDOI2013]方程
- java快速学习
- Android调用Web服务
- 在magneto系统中输出tier price的最小值
- JDBC用ResultSet访问大量数据时会遇到的问题
- HttpUtility.HtmlEncode
- phpcms9添加301跳转
- iOS 相关职位要求整理版
- ZOJ2971 Give Me the Number 【模拟】
- Android 实现在线程中联网
- Twenty Newsgroups Classification实例任务之TrainNaiveBayesJob(一)
- JTable demo
- (四)—性能测试工具curl-loader(linux)
- 远程连接SqlServer 数据库时提示 ";在与SQL Server 建立连接时出现与网络相关的或特定实例的错误"; 解决方法
- vue-2-计算属性和观察者
- scala 爬虫 去除不能存储的特殊字符
- SocketServer源码学习补充
- gdb可视化工具gdbgui
- 【luogu 1439 最长公共子序列】
- MDK stm32 仿真