最佳加法表达式

佚名 6年前 (2019-04-21) 随笔 527人围观抢沙发百度已收录

题意：
有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少。
输入：
5 3
1 2 3 4 5
输出：
24

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int str[1000];
 5 int num[1000][1000];
 6 int dp[1000][1000];
 7 int n, m;
 8 int main(void)
 9 {
10     while (cin >> n >> m)
11     {
12         int i;
13         for (i = 1; i <= n; ++i)  //读入数字串
14         {
15             cin >> str[i];
16         }
17         int j;
18         for (i = 1; i <= n; ++i)
19         {
20             num[i][i] = str[i];
21         }
22         for (i = 1; i <= n; ++i)   //计算出 num(i,j)的数值大小
23         {
24             for (j = i+1; j <= n; ++j)
25             {
26                 num[i][j] = 10 * num[i][j - 1] + str[j];
27             }
28         }
29         memset(dp, 0x3f, sizeof(dp));
30         for (i = 1; i <= n; ++i)
31         {
32             dp[0][i] = num[1][i];
33         }
34         for (i = 1; i <= m; ++i)
35         {
36             for (j = 1; j < i + 1; ++j)
37             {
38                 dp[i][j] = 0x3f;
39             }
40         }
41         int k;
42         for (i = 1; i <= m; ++i)
43         {
44             for (j = i+1 ; j <= n; ++j)
45             {
46                 for (k = i; k <= j - 1; k++)
47                 {
48                     dp[i][j] = min(dp[i][j], dp[i - 1][k] + num[k + 1][j]);     //k=i。。。。j-1
49                 }
50             }
51         }
52         cout << dp[m][n]<<endl;
53     }
54     return 0;
55 }