百练4152:最佳加法表达式（dp+高精度）

 1 import java.math.BigDecimal;
 2 import java.math.BigInteger;
 3 import java.util.Scanner;
 4 
 5 public class Main {
 6     static BigInteger INF = new BigInteger("9999999999999999999999999999999999999999999999999999999");
 7     public static void main(String[] args) {
 8         // TODO Auto-generated method stub
 9         Scanner sc = new Scanner(System.in);
10         BigInteger dp[][] = new BigInteger[55][55];
11         int m,n;
12         BigInteger s;
13         
14         while(sc.hasNext())
15         {
16             m = sc.nextInt();
17             s = sc.nextBigInteger();
18             
19             n = s.toString().length();
20             
21             //BigDecimal num[][] = new BigDecimal[n+1][n+1];//num[i][j]表示从s第i个数到第j个数组成的数字
22             /*
23             for(int i = 1;i<=n;++i)
24                 for(int j = 0;j<=n;++j)
25                 {
26                     if(i<=j)
27                     {
28                         num[i][j] = new BigDecimal(s.toString().substring(i-1,j));
29                     }
30                 }
31                 */
32             
33             dp[0][0] = new BigInteger("0");//没有数字没有加号的最小值是0
34             for(int i = 1;i<=n;++i)
35             {
36                 dp[i][0] =  new BigInteger(s.toString().substring(0,i));//没有加号的情况下，最小值就是数字自己
37             }
38             
39             for(int i = 0;i<=n;++i)
40                 for(int j = 1;j<=m;++j)
41                 {
42                     
43                     dp[i][j] = INF;
44                     if(i>=j+1)//j个加号能插入i个数字中
45                     {
46                         for(int k = j;k<i;++k)
47                         {
48                             dp[i][j] = dp[i][j].min(dp[k][j-1].add(new BigInteger(s.toString().substring(k,i))));
49                         }
50                     }
51                 }
52                 
53             System.out.println(dp[n][m]);    
54         }//while
55     }
56 
57 }