• P2308 添加括号,区间dp,dfs过程展示


    P2308 添加括号 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

    题目背景

    给定一个正整数序列a(1),a(2),...,a(n),(1<=n<=20)

    不改变序列中每个元素在序列中的位置,把它们相加,并用括号记每次加法所得的和,称为中间和。

    例如:

    给出序列是4,1,2,3。

    第一种添括号方法:

    ((4+1)+(2+3))=((5)+(5))=(10)

    有三个中间和是5,5,10,它们之和为:5+5+10=20

    第二种添括号方法

    (4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)

    中间和是3,6,10,它们之和为19。

    题目描述

    现在要添上n-1对括号,加法运算依括号顺序进行,得到n-1个中间和,求出使中间和之和最小的添括号方法。

    输入格式

    共两行。 第一行,为整数n。(1< =n< =20) 第二行,为a(1),a(2),...,a(n)这n个正整数,每个数字不超过100。

    输出格式

    输出3行。 第一行,为添加括号的方法。 第二行,为最终的中间和之和。 第三行,为n-1个中间和,按照从里到外,从左到右的顺序输出。

    输入输出样例

    输入 #1复制

    4
    4 1 2 3

    输出 #1复制

    (4+((1+2)+3))
    19
    3 6 10

    说明/提示

    范围在题目上有说明。

    解析:

    这道题实际上是石子合并的升级版本,增加了过程展示这一不。

    对于过程的展示,我没呢可以用dfs从最终答案往回搜索的到,应为最后的最优解一定是由前一个状态转移而来的,所以我们dfs最优解的状态即可。

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. using namespace std;
    16. typedef long long LL;
    17. const int N = 100;
    18. int n;
    19. int f[N][N], a[N], sum[N], flg[N][N];
    20. void print(int l, int r) {
    21. if (l == r) {
    22. printf("%d", a[l]);
    23. return;
    24. }
    25. printf("(");
    26. print(l, flg[l][r]);
    27. printf("+");
    28. print(flg[l][r] + 1, r);
    29. printf(")");
    30. }
    31. int F(int l, int r) {
    32. if (l == r) {
    33. return a[l];
    34. }
    35. int ret = F(l, flg[l][r]) + F(flg[l][r] + 1, r);
    36. printf("%d ", ret);
    37. return ret;
    38. }
    39. int main() {
    40. scanf("%d", &n);
    41. for (int i = 1; i <= n; i++) {
    42. scanf("%d", &a[i]);
    43. sum[i] = sum[i - 1] + a[i];
    44. }
    45. for (int l = 2; l <= n; l++) {
    46. for (int i = 1; i + l - 1 <= n; i++) {
    47. int j = i + l - 1;
    48. f[i][j] = 0x3f3f3f3f;
    49. for (int k = i; k + 1 <= j; k++) {
    50. if (f[i][j] > f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]) {
    51. f[i][j] = f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1];
    52. flg[i][j] = k;
    53. }
    54. }
    55. }
    56. }
    57. print(1, n);
    58. printf("\n%d\n", f[1][n]);
    59. F(1, n);
    60. return 0;
    61. }

  • 相关阅读:
    Go语音中并发介绍
    【rosrun diagnostic_analysis】报错No module named rospkg | ubuntu 20.04
    洛谷P4767 [IOI2000]邮局(决策单调DP,四边形不等式优化)
    何时以及如何使用try、catch和throw关键字
    Java学习之--类和对象
    【Rust】用RefCell避开`&mut XX`导致的借用检查
    Bootstrap 和 WordPress 的区别
    【信息科学技术与创新】机器学习 深度学习 人工神经网络相关分析
    PHP7和PHP8的新特性
    Kubernetes-基础(Namespace,Pod,Lable,Deployment,Service)
  • 原文地址:https://blog.csdn.net/Landing_on_Mars/article/details/134038352