HIT2013算法设计与分析第5题
2022/5/24 1:19:56
本文主要是介绍HIT2013算法设计与分析第5题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给出N个1-9的数字 (v1,v2,…,vN),不改变它们的相对位置,在中间加入K个乘号和N-K-1个加号,(括号随便加)使最终结果尽量大。因为乘号和加号一共就是N-1个了,所以恰好每两个相邻数字之间都有一个符号。并说明其具有优化子结构性质及子问题重叠性质。
例如: N=5, K=2,5个数字分别为1、2、3、4、5,可以加成:
1*2*(3+4+5)=24
1*(2+3)*(4+5)=45
(1*2+3)*(4+5)=45
考虑终态,dp[n][m]表示前n个数,有m个乘法的最大值,
它的前驱状态为dp[k][m - 1] * prefix(k + 1, n), 其中k∈[1, n-1],prefix为k + 1~n的区间和
状态转移方程为
dp[i][j] = max(dp[i][j], dp[k][j - 1] * prefix(k + 1, i))
这篇关于HIT2013算法设计与分析第5题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?