CSUOJ 1952 合并石子
2024-10-16 02:21:36
现在有n堆石子,第i堆有ai个石子。现在要把这些石子合并成一堆,每次只能合并相邻两个,每次合并的代价是两堆石子的总石子数。求合并所有石子的最小代价。
Input
第一行包含一个整数T(T<=50),表示数据组数。
每组数据第一行包含一个整数n(2<=n<=100),表示石子的堆数。
第二行包含n个正整数ai(ai<=100),表示每堆石子的石子数。
Output
每组数据仅一行,表示最小合并代价。
Sample Input
2
4
1 2 3 4
5
3 5 2 1 4
Sample Output
19
33
题解:区间DP,dp[i][j]表示以i开始区间为j长的费用最小值;则状态转移方程为:dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cstdlib>
#include<set>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
int T,N,w[],dp[][],pre[]; int main()
{
ios::sync_with_stdio(false);
cin.tie();
cin>>T;
while(T--)
{
memset(dp,,sizeof dp);
memset(pre,,sizeof pre);
cin>>N;
for(int i=;i<=N;i++) cin>>w[i],pre[i]=pre[i-]+w[i]; for(int i=;i<=N;i++)
{
for(int j=;j<=N-i;j++)
{
dp[j][j+i]=INF;
for(int k=j;k<=j+i-;k++)
dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k+][j+i]+pre[j+i]-pre[j-]);
}
}
cout<<dp[][N]<<endl;
} return ;
}
最新文章
- HashMap与TreeMap源码分析
- 让OData和NHibernate结合进行动态查询
- php中引用&;的真正理解-变量引用、函数引用、对象引用
- Android课程---序列化与反序列化(转)
- NotePad++常用快捷键。——Arvin
- c++成员函数的存储方式---11
- 关于 iOS 10 中 ATS / HTTPS /2017 问题
- dos基本命令
- phaser运用中,dota战术板
- Spring JDBC主从数据库配置
- MVC 文本转换成html显示
- EF简介
- Glide4 用法总结 MD
- docker上部署nginx容器80端口自动转443端口
- [Node.js] Availability and Zero-downtime Restarts
- 【服务器_Tomcat】Tomcat的Server Options选项
- python的可变数据类型和不可变类型
- RocketMQ读书笔记5——消息队列的核心机制
- 用CSS使图片上下左右都绝对居中于DIV
- &#39;javac&#39; 不是内部或外部命令,也不是可运行的程序
热门文章
- 队列+BFS(附vector初试)
- 分析facebook的AsyncDisplayKit框架,async-display使用async-transaction
- 解决failed to push some refs to &#39;git@github.com:TQBX/GIT-Github-.git&#39;问题
- 使用Query Store监控性能
- 常见 MIME 类型列表(转)
- Windows之Java开发环境快速搭建
- Java异常处理只有Try-Catch吗?
- 解决&ldquo;无法完成域加入,原因是试图加入的域的SID与本计算机的SID相同
- Intellij 生成exe可执行文件
- Elasticsearch系列---并发控制及乐观锁实现原理