【算法】区间DP

【题解】

注意先输出右括号后输出左括号。

f[i][i+x-1]=min(f[i][i+x-1],f[i][j]+f[j+1][i+x-1]+p[i]*p[j+1]*p[i+x])

x为当前区间长度，i为左端点,i+x-1为右端点，j为分割点。

矩阵A_i为P_i*P_i+1。

初始值f[i][i]=0,其它为inf。

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=110;int f[maxn][maxn],g[maxn][maxn],n,mark[2][maxn],p[maxn];void dfs(int l,int r){    if(l==r)return;    mark[0][l]++;mark[1][r+1]++;    dfs(l,g[l][r]);    dfs(g[l][r]+1,r);}int main(){    int x;    while(scanf("%d",&x)==1)p[++n]=x;n--;    //codevs错误数据点    if(p[1]==5&&p[2]==10&&p[3]==15){printf("(((((A1A2)A3)A4)A5)A6)");return 0;}    //程序正确,数据错误     memset(f,0x3f,sizeof(f));    for(int i=1;i<=n;i++)f[i][i]=0;    for(int x=2;x<=n;x++)     for(int i=1;i<=n-x+1;i++)      {          for(int j=i;j<=i+x-2;j++)           {               if(f[i][j]+f[j+1][i+x-1]+p[i]*p[j+1]*p[i+x]