JHwong

用户名：dotcpp0724243

访问量：832

签　名：

等　　级
排　　名	3383
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

1435: 蓝桥杯历届试题-国王的烦恼
浏览：156

1427: 蓝桥杯2013年第四届真题-买不到的数目
浏览：39

2529: NOIP2012-同余方程-了解即可
浏览：34

你可能喜欢

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

最大的算式

　　作者: JHwong　　　　发表时间：2024-01-12 00:06:33 浏览：33　|　评论：0　

原题链接：最大的算式

#最大的算式
##思路解析
这道题是一道明显的动态规划题。因为状态上是叠加的。状态中有依赖关系，或者说有约束关系。但是这种约束是可以模糊化的，也就是不用明确知道过去的状态具体如何。dp数组设计详见代码实现中的注释部分
##代码实现
```cpp
/* 
 * 题目 1312: 最大的算式
 * dp[i][j][k] = [i,j]中有k个乘法,
 * dp[i][j][k] = dp[i][j'][k'] + dp[j' + 1][j][k - k'];  0 <= k <= j - i
 * 事实上因为需要求取[1, N]，所以(i != 1, ...)的信息都是我们不需要的，所以可以舍弃
 * dp[j][k] = [1, j]中有k个乘法.
 * dp[j][k] = dp[j' - 1][k - 1] * (sum of [j', j]), j' <= j and k <= j - 1 and k <= number of multiplition
 */
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX_NUMBER_OF_DIGIT 16
#define MAX_NUMBER_OF_MULTIPLITION 16
int sum[MAX_NUMBER_OF_DIGIT];
int number_of_digit, number_of_multiplition;
int dp[MAX_NUMBER_OF_DIGIT][MAX_NUMBER_OF_MULTIPLITION];

int main() {
  scanf("%d %d", &number_of_digit, &number_of_multiplition);
  int x;
  for (int i = 1; i <= number_of_digit; ++i) {
    scanf("%d", sum+ i);
    sum[i] += sum[i - 1];
  }

for (int i = 1; i <= number_of_digit; ++i) dp[i][0] = sum[i];
  for (int i = 2; i <= number_of_digit; ++i)
  {
    int max_k = std::min(i - 1, number_of_multiplition);
    for (int k = 1; k <= max_k; ++k)
      for (int j = 1; j < i; ++j)
        dp[i][k] = std::max(dp[i][k], dp[j][k - 1] * (sum[i] - sum[j]));
  }
  printf("%d", dp[number_of_digit][number_of_multiplition]);
  return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言训练-立方和不等式（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

A+B for Input-Output Practice (V) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

最大的算式

评论区

精彩推荐

点我有惊喜！你懂得！

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

数组输出（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

WU-字符串比较（C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

1012题解

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言训练-立方和不等式 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

A+B for Input-Output Practice (V) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

最大的算式

评论区

精彩推荐

点我有惊喜！你懂得！

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

数组输出 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

WU-字符串比较 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

1012题解

C语言训练-立方和不等式（C语言代码）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

数组输出（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

WU-字符串比较（C++代码）