E 凸多边形的划分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=55;
 4 inline void read(__int128 &X)
 5 {
 6     X = 0;
 7     int w=0; char ch=0;
 8     while(!isdigit(ch)) {w|=ch==‘-‘;ch=getchar();}
 9     while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
10     if (w) X = -X;
11 }
12 inline void print(__int128 x)
13 {
14     if (!x) return ;
15     if (x < 0) putchar(‘-‘),x = -x;
16     print(x / 10);
17     putchar(x % 10 + ‘0‘);
18 }
19 __int128 dp[maxn][maxn]; int a[maxn];
20 const __int128 INF=1e30;
21 int main(void)
22 {
23     int n; scanf("%d",&n);
24     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
25     for(int len=3;len<=n;len++)
26     {
27         for(int i=1;i+len-1<=n;i++)
28         {
29             int j=i+len-1; 
30             dp[i][j]=INF;
31             for(int k=i+1;k<=j-1;k++)
32             {
33                 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+(__int128)a[i]*a[j]*a[k]);
34             }
35         }
36     }
37     print(dp[1][n]); printf("\n");
38     return 0;
39 }

 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3 public class Main{
 4     public static void main(String[] args) {
 5         Scanner cin=new Scanner(System.in);
 6         while(cin.hasNext()){
 7             int n=cin.nextInt();
 8             BigInteger []a= new BigInteger[n+10];
 9             BigInteger[][]dp= new BigInteger[100][100];
10             for(int i=1;i<=n;i++){
11                 a[i]=cin.nextBigInteger();
12             }
13             for(int i=0;i<100;i++){
14                 for(int j=0;j<100;j++){
15                     dp[i][j]=new BigInteger("134567456745674567567567567134567456745674567567567567");
16                 }
17             }
18             for(int i=n;i>=1;i--){
19                 for(int j=i+1;j<=n;j++){
20                     if(j-i==1){
21                         dp[i][j]=BigInteger.ZERO;
22                     }
23                     else if(j-i==2){
24                         dp[i][j]=a[i].multiply(a[i+1].multiply(a[i+2]));
25                     }else{
26                         for(int k=i+1;k<=j-1;k++){
27                             BigInteger pre=dp[i][k].add(dp[k][j].add(a[i].multiply(a[j].multiply(a[k]))));
28                             if(dp[i][j].compareTo(pre)==1){
29                                 dp[i][j]=pre;
30                             }
31                         }
32                     }
33                 }
34             }
35             System.out.println(dp[1][n]);
36         }
37     }
38 }