蓝桥杯 最大的算式

 1 #include <bits/stdc++.h> 
 2 using namespace std;
 3 long long dp[20][20];
 4 long long sum[20];
 5 int main() {
 6     int n, k;
 7     cin >> n >> k;
 8     for(int i = 1; i <= n; i++) {
 9         int t;
10         cin >> t;
11         sum[i] = sum[i - 1] + t;
12         dp[i][0] = sum[i]; 
13     }
14     for(int i = 2; i <= n; i++) { //数字个数逐渐增加 
15         for(int j = 1; j <= i - 1 && j <= k; j++) { //乘号个数逐渐增加 
16             for(int p = 2; p <= i; p++)    { //乘号的位置逐渐往后移  
17                 dp[i][j] = max(dp[i][j], dp[p - 1][j - 1] * (sum[i] - sum[p - 1]));
18             }
19         }
20     }
21     cout << dp[n][k] << endl;
22     return 0;
23  }