vijosP1038 添加括号

vijosP1038 添加括号

链接：https://vijos.org/p/1038

【思路】

   区间DP。

   本题的关键在于如何输出解。对于求和表达式而言可以用一个p[][]记录决策然后递归输出，对于部分和而言可以在递归的同时用一个ans保存。

   本题需要注意的就是从左到右由里到外的输出顺序，就是如果部分和相等则记录k大的一个决策。

【代码】

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int maxn = 100+10;

int a[maxn],d[maxn][maxn];
int suma[maxn],p[maxn][maxn];
vector<int> ans;
int n;

void print(int i,int j) {
    if(i==j) cout<<a[i];
    else {
        cout<<'(';
        print(i,p[i][j]);
        cout<<'+';
        print(p[i][j]+1,j);
        cout<<')';
        ans.push_back(suma[j]-suma[i-1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    memset(d,60,sizeof(d));
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i] ;
    suma[0]=0;
    for(int i=1;i<=n;i++) suma[i] += suma[i-1]+a[i] , d[i][i]=a[i]; 
    
    for(int l=1;l<=n;l++)
       for(int i=1;i+l<=n;i++)
       {
              int j=i+l;
           for(int k=i;k<j;k++)
           {
              int tmp=d[i][k]+d[k+1][j]+suma[j]-suma[i-1];
              if(d[i][j]>=tmp) {
                    d[i][j]=tmp;
                    p[i][j]=k;
              }
           }
       }
    print(1,n);
    cout<<"
"<<d[1][n]-(suma[n]-suma[0])<<"
";
    for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
    return 0;
}