算法提高 矩阵乘法 蓝桥杯

　　1<=n<=1000, 1<=ai<=10000。

类似于合并石子问题

子问题：矩阵i到j合并最小花费

一开始dp数组用longlong，行列数用int，数据较大时答案错误，都改成longlong就好了，但是最后一组运行超时。

#include<stdio.h>#define min(a,b) a<b?a:bint n;long long dp[2000][2000]={0};struct Matrix{long long l;long long c;}b[2000];long long f(int u,int v){int k;long long q=99999999999999999;if(u==v)return 0;if(dp[u][v]) return dp[u][v];for(k=u;k<v;k++){  q=min(q,f(u,k)+f(k+1,v)+b[u].l*b[k].c*b[v].c);}return dp[u][v]=q;}int main(){int i;scanf("%d",&n);for(i=0;i<=n;i++){    scanf("%lld",&b[i].c);    b[i+1].l=b[i].c;}PRintf("%lld",f(1,n));return 0;}