Luogu P2308 添加括号 (记忆化搜索)

发表于 更新于 分类于

题目

题目背景

给定一个正整数序列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： 

1
2
4
4 1 2 3
输出样例#1： 
1
2
3
(4+((1+2)+3))
19
3 6 10
## 说明

范围在题目上有说明。 # 题解

记忆化搜索

dp[i][j]表示n个数以i为开头j为结尾的子串的答案

建立一个结构体来定义dp[][]，其中： 1. value表示当前区间的中间值总和，如样例中dp[1][n].value为19 2. sum表示当前区间的数的和，用来维护上一层递归的value 3. program表示当前区间的加+方案，是string类 4. midsum表示当前区间取过的中间值，具体使用方法后面讲

记忆化部分不再赘述，要加的一定要加不然会TLE

设当前枚举到了[i, k]和[k + 1, j]两个区间

  1. 新的区间和dp[i][j].sum = dp[i][k].sum + dp[k + 1][j].sum

  2. 得到的中间值总和为左右两区间中间值总和的和加上新产生的区间和，即dp[i][j].value = dp[i][k].value + dp[k + 1][j].value + dp[i][j].sum, 更新条件为新值小于等于原值 (此处要注意，没有等于会WA两个点，目前原因我分析出来是洛谷没开Special Judge······)

  3. program和midsum直接string的+运算就可以了

输出答案时，program和value正常输出，midsum用stringstream处理后再输出，如果不会点这里

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define MERGE(str1, str2) string("(") + str1 + "+" + str2 + ")"
struct number {
  int value, sum;
  string program, midsum;
  number() {
    value = sum = 0;
  }
} dp[30][30], ans;
int n, arr[30];
inline number Dfs(const int &left, const int &right) {
  register number ret;
  if (dp[left][right].value) return dp[left][right];
  if (left == right) {
    ret.sum = arr[left];
    register char tmp[10];
    sprintf(tmp, "%d", arr[left]);
    ret.program = string(tmp);
    return dp[left][right] = ret;
  }
  register number tmp1, tmp2;
  ret.value = 10000;
  for (register int i(left); i < right; ++i) {
    tmp1 = Dfs(left, i);
    tmp2 = Dfs(i + 1, right);
    if (tmp1.sum + tmp2.sum + tmp1.value + tmp2.value <= ret.value) {
      ret.value = tmp1.value + tmp2.value + tmp1.sum + tmp2.sum;
      ret.sum = tmp1.sum + tmp2.sum;
      ret.program = MERGE(tmp1.program, tmp2.program);
      register char tmp[10];
      sprintf(tmp, "%d", ret.sum);
      ret.midsum = tmp1.midsum + string(" ") + tmp2.midsum + string(" ") + tmp;
    }
  }
  return dp[left][right] = ret;
}
int sums[30]; 
int main(int argc, char **argv) {
  scanf("%d", &n);
  for (register int i(1); i <= n; ++i) scanf("%d", &arr[i]);
  ans = Dfs(1, n);
  register stringstream ss;
  ss << ans.midsum;
  for (register int i(0); i < n - 1; ++i) ss >> sums[i];
  cout << ans.program << endl << ans.value << endl;
  for (register int j(0); j < n - 1; ++j) cout << sums[j] << " ";
  return 0; 
}

其他

LIPI让我帮他做。。。

我都不相信我做出了DP题