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;}