[HOJ] 46 正值DE

參考這個
dp[i][i+L]表示從第i個矩陣乘到第i+L的最佳解

每次尋找i~L之間的最佳中間點k
dp[i][i+L]=min(dp[i][i+L],dp[i][k]+dp[k+1][i+L]+R[i]*C[k]*c[i+L])

#include<cstdio>
#define MAX 1005
#define LL long long
int n,r[MAX],c[MAX],T;
LL dp[MAX][MAX],tmp,ans,cnt;
LL min(LL a,LL b){
    return a<b? a:b;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&r[i],&c[i]);
        for(int L=1;L<n;L++){
            for(int i=1;i+L<=n;i++){
                tmp=9*(10e18);
                for(int k=i;k<i+L;k++){
                    tmp=min(tmp,dp[i][k]+dp[k+1][i+L]+r[i]*c[k]*c[i+L]);
                }
                dp[i][i+L]=tmp;
            }
        }
        ans=dp[1][n];
        cnt+=ans;
        printf("%lld\n",(ans-1)/1000+1);
    }
    printf("%lld\n",(cnt-1)/1000+1);
}