添加括号

cmwqf · 2018-05-07 22:16:35 · 个人记录

主要要注意输出格式的巧妙递归，十分有用。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxN=25;
int sum[maxN+1],dp[maxN+1][maxN+1],rec[maxN+1][maxN+1],n;
int left[maxN+1],right[maxN+1];
void dfs(int x,int y)
{
    if(x==y) return;
    left[x]++,right[y]++;
    dfs(x,rec[x][y]);
    dfs(rec[x][y]+1,y);
}
void print(int x,int y)
{
    if(x==y) return;
    print(x,rec[x][y]);
    print(rec[x][y]+1,y);
    printf("%d ",sum[y]-sum[x-1]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        sum[i]=sum[i-1]+x;
    }
    for(int i=n-1;i>=1;i--)
       for(int j=i+1;j<=n;j++)
       {
           dp[i][j]=0x3f3f3f3f;
           for(int k=i;k<j;k++)
              if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]<=dp[i][j])
              //坑点啊，<=，因为从左到右，最右边的最佳； 
              {
                  rec[i][j]=k;
                  dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
              }
       }     
    dfs(1,n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=left[i];j++) printf("(");
        printf("%d",sum[i]-sum[i-1]);
        if(left[i]&&i!=n) printf("+");
        for(int j=1;j<=right[i];j++) printf(")");
        if(i!=n&&!left[i]) printf("+");
    }
    printf("\n%d\n",dp[1][n]);
    print(1,n);
    return 0;
}
/*
dp[i][j]表示再第i个和第j个处加一个括号的最小值；
dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
*/