vijosP1038 添加括号

vijosP1038 添加括号

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

【思路】

区间DP。

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

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

【代码】

 #include<iostream>

 #include<cstring>

 #include<vector>

 using namespace std;

 const int maxn = +;

 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]+,j);

         cout<<')';

         ans.push_back(suma[j]-suma[i-]);

     }

 }

 int main() {

     ios::sync_with_stdio(false);

     memset(d,,sizeof(d));

     cin>>n;

     for(int i=;i<=n;i++) cin>>a[i] ;

     suma[]=;

     for(int i=;i<=n;i++) suma[i] += suma[i-]+a[i] , d[i][i]=a[i];

     for(int l=;l<=n;l++)

        for(int i=;i+l<=n;i++)

        {

               int j=i+l;

            for(int k=i;k<j;k++)

            {

               int tmp=d[i][k]+d[k+][j]+suma[j]-suma[i-];

               if(d[i][j]>=tmp) {

                     d[i][j]=tmp;

                     p[i][j]=k;

               }

            }

        }

     print(,n);

     cout<<"\n"<<d[][n]-(suma[n]-suma[])<<"\n";

     for(int i=;i<ans.size();i++) cout<<ans[i]<<" ";

     return ;

 }