nyoj-737--石子合并(一)(动态规划)
2024-09-07 02:19:36
石子合并(一)
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
- 有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。
/*dp数组中存放合并i--j所需要的最少代价,局部最优达到整体最优,刚开始
从一个到两个*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 0x3f3f3f
int dp[210][210];
int a[210];
int sum[210];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
memset(dp,0,sizeof(dp));
for(int i=n;i>=1;i--)
{
for(int j=i+1;j<=n;j++)
//i和j固定了起点和终点,k相当于节点,通过变换k来达到i--j最优
{
int temp=MAX;
for(int k=i;k<j;k++)//k!=j,因为同一堆石子不能合并
temp=min(temp,dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
dp[i][j]=temp;
}
}
printf("%d\n",dp[1][n]);
}
return 0;
}
最新文章
- 利用StringEscapeUtils对字符串进行各种转义与反转义(Java)
- 【转】WPF 单选的Checkbox
- mysql,命令导入\导出表结构或数据
- live555库中的testRTSPClient实例
- 从一个QQ群友那儿偷来的js图形 ^_^
- shell中&;&;和||的使用方法
- Java多线程-线程的调度(守护线程)
- hibernate--持久对象的生命周期介绍
- 【Java】Web 服务编程技巧与窍门: 在 UDDI 注册中心为 Web 服务注册开发 UDDI Java 应用程序
- Java 二次MD5 32位小写加密算法与php页面加密结果相同
- Foundations of Computer Science
- 当final作用于变量、参数、方法和类时该如何处理
- 参照企业微信审批业务,在Winform开发框架中工作流模块的实现业务审批
- java中抽象类的概念
- Python中模块之os的功能介绍
- virltualbox 升级之后 苹果虚拟机报The installed support driver doesn&#39;t match the version of the user解决方案
- SQLServer 清空某个库所有表
- Dubbo+zookeeper面试题补充
- InstallShield 读注册表函数 RegDBGetKeyValueEx ()执行失败
- Python地理位置信息库geopy的使用(一):基本使用
热门文章
- intelliJ idea运行新的test功能时,报错:class not found ";....."; empty test suite
- 7.gcc的使用
- 关于requestAnimationFrame()和cancelAnimationFrame()与定时器之间的比较
- HDU 2955 Robberies【01背包】
- RunLoop主要处理以下6类事件
- Unity 烘焙的2种方式
- node——含有异步函数的函数封装
- windows下Word使用-快捷键
- HDU 5776 sum( 鸽巢定理简单题 )
- Ansible学习记录四:单命令测试