划分型动态规划-基于labview和fpga的多通道虚拟逻辑分析仪的设计
13.9划分型动态规划13.9.1乘积最大描述设有一个长度为N的数字串，要求选手使用K个乘号将它分成K + 1个部分，找出一种分法，使得这K + 1个部分的乘积能够为最大。举个例子：有一个数字串：312，当N = 3，K = 1时会有以下两种分法： • 3*12=36 • 31*2=62这时，符合题目要求的结果是：31*2=62。输入输入共有两行：第一行共有2个自然数N,K(6 ≤ N ≤ 40, 1 ≤ K ≤ 6)第二行是一个长度为N的数字串。输出输出最大乘积样例输入4 2 1231样例输出62分析首先，本题可以用区间型动态规划的思路解决。设状态为f[i][j][k]，表示i到j这一段用k个乘号的最大乘积，状态转移方程如下： f [i][j][k] = max {f [i][s][t] ∗ f [s+ 1][j][k − t− 1]} , i ≤ s < j, 0 ≤ t < k复杂度是O(N3K2)，代码如下：
文件大小：2.99MB
评论区