E题

E题题解

正常的区间DP，dp[i][j]表示[i,j]这个区间的划分的最小乘积，然后枚举k转移，这里需要判断i和j中间点的个数，是不是符合三角形的规则。然后由于数据比较大，1e9^3,所以用JAVA来一发基本ok。

import java.math.BigInteger;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            int n=cin.nextInt();
            BigInteger []a=new BigInteger[n+10];
            BigInteger[][]dp=new BigInteger[100][100];
            for(int i=1;i<=n;i++){
                a[i]=cin.nextBigInteger();
            }
            for(int i=0;i<100;i++){
                for(int j=0;j<100;j++){
                    dp[i][j]=new BigInteger("134567456745674567567567567134567456745674567567567567");
                }
            }
            for(int i=n;i>=1;i--){
                for(int j=i+1;j<=n;j++){
                    if(j-i==1){
                        dp[i][j]=BigInteger.ZERO;
                    }
                    else if(j-i==2){
                        dp[i][j]=a[i].multiply(a[i+1].multiply(a[i+2]));
                    }else{
                        for(int k=i+1;k<=j-1;k++){
                            BigInteger pre=dp[i][k].add(dp[k][j].add(a[i].multiply(a[j].multiply(a[k]))));
                            if(dp[i][j].compareTo(pre)==1){
                                dp[i][j]=pre;
                            }
                        }
                    }
                }
            }
            System.out.println(dp[1][n]);
        }
    }
}