P1291-添加括号(区间dp)

题目背景

给定一个正整数序列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个中间和,按照从里到外,从左到右的顺序输出。


一道很有价值的区间dp,一共包含了3个子问题;首先用区间dp求出f[i][j]及i-j之间最小的累加和,很显然有:

for(int len = 2; len <= n; ++len) {
        for(int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            for(int i = l; i < r; ++i) 
                f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]); 
            f[l][r] += sum[r] - sum[l - 1]; 
        }
    }

接着用dfs枚举区间来求出括号的方案,同时求出所有区间的和,用ans作为序号便于输出,这样就A掉了,个别细节需要注意,切切切~~

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 100;
const int MAXM = 3e3 + 10;

inline int read() {
    int x = 0, ff = 1; char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') ff = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * ff;
}

inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int n, ans, a[MAXN], sum[MAXN], f[MAXM][MAXM];
priority_queue < pair < int, int > > q;

void dfs(int l, int r) {
    if(l == r) {
        write(a[l]);
        return ;
    }
    for(int i = r; i >= l; --i) { // 倒序,为了使方案等效时,以括弧靠左为优先~ 
        if(f[l][i] + f[i + 1][r] + sum[r] - sum[l - 1] == f[l][r]) { // 好好思考~ 
            putchar('(');
            dfs(l, i);
            putchar('+');
            dfs(i + 1, r);
            putchar(')');
            q.push(make_pair(-(++ans), sum[r] - sum[l - 1]));
            return ;
        }
    }
}

int main() {
    memset(f, 0x3f, sizeof(f)); 
    n = read(); 
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        f[i][i] = 0; 
        sum[i] = sum[i - 1] + a[i];
    }
    for(int len = 2; len <= n; ++len) {
        for(int l = 1; l <= n - len + 1; ++l) {
            int r = l + len - 1;
            for(int i = l; i < r; ++i) 
                f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]); 
            f[l][r] += sum[r] - sum[l - 1]; 
        }
    }
    dfs(1, n); 
    putchar('\n');
    write(f[1][n]);
    putchar('\n');
    while(!q.empty()) {
        int x = q.top().second; q.pop();
        write(x); 
        putchar(' ');
    } 
    return 0; 
}

 

上一篇:【AtCoder】AGC018


下一篇:getchar()和putchar()