Bamboo和人工ZZ

题意：

非常直白，经典的动态规划矩阵链乘问题

分析：

矩阵链A1A2..An满足结合律，可以使用加括号的方式，降低运算代价。

一个pq的矩阵和一个qr的矩阵相乘，计算代价为pqr

加括号时满足动态规划的特性

长度为1的矩阵不需要加括号

长度>=2的矩阵链AiAi+1.....Aj，势必在 Ak和Ak+1之间加括号，分成的两组中各自的加括号方案已经是最优的了。

以m[i][j]表示Ai-Aj矩阵链乘的代价，则

核心语句：

i=j m[i][j]=0;

i<j m[i][j] = min(m[i][k] + m[k+1][j] + pi-1pkpj); i<=k<j

l:矩阵链长度，长度为1无需考虑

i：与j遍历所有长度为l的矩阵链

k:遍历所有可能的分割点

保留最小的方案

输出括号化方案，s[i][j]记录分割点k，递归输出方案。注意左边优先，有两种方式，可以在判断if(q<=m[i][j])时加上等号；或者内层的k循环倒序

伪代码

int p[]

int m[][]

int s[][]

void Multiply()

{

    Initialization of m[][]

    for l = 2:n

        for i = 1: n-l+1

        j = i+l-1

        m[i][j]= INF

        for  k = i:=j-1

             q = m[i][k]+m[k+1][j]+ p[i-1]*p[k]*p[j]

            if(q<=m[i][j])

                m[i][j] = q

                s[i][j] = k

            end

        end

     end

}

void Print( i, j)

{

    if(i==j)

        printf("A%d",i)

    else

        printf("(")

        Print(i,s[i][j])

        Print(s[i][j]+1, j)

        printf(")")

    end

}

代码如下：

#include<stdio.h>

#include<math.h>

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

int p[310];

int m[305][305];

int s[305][305];

const int INF = 1<<30;

void Mulity(int n)

{

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

        m[i][i] = 0;

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

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

    {

        int j = i+l-1;

        m[i][j]= INF;

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

        {

            int q = m[i][k]+m[k+1][j]+ p[i-1]*p[k]*p[j];

            if(q<=m[i][j])

            {m[i][j] = q;

            s[i][j] = k;

            }

        }

    }

}

void Print(int i,int j)

{

    if(i==j)

        printf("A%d",i);

    else

    {

        printf("(");

        Print(i,s[i][j]);

        Print(s[i][j]+1, j);

        printf(")");

    }

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

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

            scanf("%d",&p[i]);

        Mulity(n);

        printf("%d\n",m[1][n]);

        Print(1,n);

        printf("\n");

    }

    }

巴特西

2016级算法第四次上机-A.Bamboo 和人工zz

Bamboo和人工ZZ

题意：

分析：

伪代码

代码如下：

最新文章

热门文章