最优矩阵链乘

 

dp[i][j] 第i个矩阵到第j个矩阵相乘的最小次数  k是分割点

蓝桥 算法提高  矩阵乘法

裸题，注意不能用min函数，会超时

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e3+10;
const int INF=0x3f3f3f3f;
typedef long long LL;
LL ans=0;
LL a[N];
LL dp[N][N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<=n;++i)     //n+1个数      a[i-1]是第i个矩阵的行数 a[i]是第i个矩阵的列数
        scanf("%lld",&a[i]);
    memset(dp,INF,sizeof(dp));
    for(int i=1;i<=n;++i)
        dp[i][i]=0;
    for(int l=2;l<=n;++l)   //枚举矩阵链乘的长度
    {
        for(int i=1;i+l-1<=n;++i)
        {
            //枚举链乘起始位置
            int j=i+l-1;    //j为链的末尾
            for(int k=i;k<=j-1;++k)     //枚举分割点
            {
                LL q=dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];
                if(q<dp[i][j])
                    dp[i][j]=q;
            }
        }
    }
    printf("%lld\n",dp[1][n]);
    return 0;

}

蓝桥 算法提高 合并石子

题意：在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。

先考虑两个石子 最小花费就是他们的和

三个石子时，（a1a2）a3 sum=a1+a2+a1+a2+a3;   a1（a2a3） sum=a2+a3+a2+a3+a1

我们可以发现这个问题和最优矩阵链乘是一个性质 都是要用分治法，把石子分成两堆，每堆石子的和尽可能小

代码超时，上题代码复杂度是n^3, 四边形不等式优化，时间复杂度降到n^2

核心思路是：1、满足四边形不等式优化的条件 2、dp[i][j]的最优分割点p[i][j]具有单调性

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e3+10;
const int INF=0x3f3f3f3f;
int sum[N];         //记录前i个石子堆总重，前缀和计算区间重量
int dp[N][N];       //记录合并第i个到第j个石子堆需要的最小花费
int p[N][N];
int main()
{
    int n;
    scanf("%d",&n);
    sum[0]=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&sum[i]);
        sum[i]+=sum[i-1];
    }

    for(int i=1;i<=n;++i)
    {
         dp[i][i]=0;
         p[i][i]=i;
    }
     for(int l=2;l<=n;++l)       //枚举石头堆范围
    {
        for(int i=1;i+l-1<=n;++i)   //枚举石头堆起始位置
        {
            int j=i+l-1;            //最后一个石头堆
            dp[i][j]=INF;
            for(int k=p[i][j-1];k<=p[i+1][j];++k)       //由于是按照区间长度来更新的，所以p[i+1][j]比p[i][j]早更新到
            {
                int tmp=dp[i][k]+dp[k+1][j];
                if(dp[i][j]>tmp)
                {
                    dp[i][j]=tmp;
                    p[i][j]=k;      //p[i][j]记录的是合并第i堆到第j堆的最优分割点
                }

            }
            dp[i][j]+=sum[j]-sum[i-1];
        }
    }


    printf("%d\n",dp[1][n]);
    return 0;
}