Luogu P2308 添加括号 题解及心得

发表于 | 分类于

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。

不难得出状态转移方程：

1
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1])

解题思路：

  1. 先区间dp，逆向枚举i，正向枚举j，阶段k=i,k<j。由于括号添加时要尽可能靠左，所以当新值<=f[i][j]时即发生更新。

    //求最小值时i逆序j正序，最大值时都正序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for(i=n-1;i;i--)
    {
        for(j=i+1;j<=n;j++)
        {
            for(k=i;k<j;k++)
            {
                int t=f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
                if(t<=f[i][j]) f[i][j]=t,g[i][j]=k;
            }
        }
    }

  2. 为了能解决第二问和第三问，令g[i][j]=k保存从下标i~j之间断点k的位置。

  3. 对于第二问，递归查找每个点左边有多少个左括号，右边有多少个右括号，然后输出。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void search(int x,int y)
    {
        if(x==y) return;
        l[x]++;
        r[y]++;
        search(x,g[x][y]);
        search(g[x][y]+1,y);
    }
    for(i=1;i<=n;i++)
    {
        for(j=0;j<l[i];j++) printf("(");
        printf("%d",a[i]);
        if(r[i]==0&&i<n) printf("+");
        for(j=0;j<r[i];j++) printf(")");
        if(r[i]>0&&i<n) printf("+");
    }

  4. 对于第三问，递归求每个中间和，然后输出。

    1
    2
    3
    4
    5
    6
    7
    void dfs(int x,int y)
    {
        if(x==y) return;
        dfs(x,g[x][y]);
        dfs(g[x][y]+1,y);
        ans[top++]=sum[y]-sum[x-1];
    }

心得：虽然大部分区间dp是在最外层枚举阶段，但是偶尔也要像这题这样最内层枚举阶段吧。//还有可能是我没想到最外层枚举阶段的做法（小声）。

总之，終わり！

<附送全篇代码>

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#define maxn(a,b) (a>b)?a:b
#define minn(a,b) (a<b)?a:b
#define maxnn(a,b,c) (a>b&&a>c)?a:((b>a&&b>c)?b:c)
#define ll long long
int a[30]={0},f[30][30],g[30][30],sum[30]={0},l[30],r[30],ans[30],top;
void search(int x,int y)
{
    if(x==y) return;
    l[x]++;
    r[y]++;
    search(x,g[x][y]);
    search(g[x][y]+1,y);
}
void dfs(int x,int y)
{
    if(x==y) return;
    dfs(x,g[x][y]);
    dfs(g[x][y]+1,y);
    ans[top++]=sum[y]-sum[x-1];
}
int main()
{
    int n,i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        top=0;
        memset(ans,0,sizeof(ans));
        memset(sum,0,sizeof(sum));
        memset(a,0,sizeof(a));
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        memset(g,0,sizeof(g));
        memset(f,1,sizeof(f));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            f[i][i]=0;
        }
        for(i=1;i<=n;i++) sum[i]=a[i]+sum[i-1];
        for(i=n-1;i;i--)
        {
            for(j=i+1;j<=n;j++)
            {
                for(k=i;k<j;k++)
                {
                    int t=f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
                    if(t<=f[i][j]) f[i][j]=t,g[i][j]=k;
                }
            }
        }
        search(1,n);
        for(i=1;i<=n;i++)
        {
            for(j=0;j<l[i];j++) printf("(");
            printf("%d",a[i]);
            if(r[i]==0&&i<n) printf("+");
            for(j=0;j<r[i];j++) printf(")");
            if(r[i]>0&&i<n) printf("+");
        }
        printf("\n%d\n",f[1][n]);
        dfs(1,n);
        for(i=0;i<top;i++)
        {
            if(i<top-1) printf("%d ",ans[i]);
            else printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}
--It's the end.Thanks for your read.--