1 /***Good Luck***/ 2 #define _CRT_SECURE_NO_WARNINGS 3 #include <iostream> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #include <stack>10 #include <map>11 #include <queue>12 #include <vector>13 #include <set>14 #include <functional>15 #include <cmath>16 #include <numeric>17 18 #define Zero(a) memset(a, 0, sizeof(a))19 #define Neg(a)  memset(a, -1, sizeof(a))20 #define All(a) a.begin(), a.end()21 #define PB push_back22 #define inf 0x3f3f3f3f23 #define inf2 0x7fffffffffffffff24 #define ll long long25 using namespace std;26 //#pragma comment(linker, "/STACK:102400000,102400000")27 void get_val(int &a) {28     int value = http://www.mamicode.com/0, s = 1;29     char c;30     while ((c = getchar()) == ‘ ‘ || c == ‘\n‘);31     if (c == ‘-‘) s = -s; else value = http://www.mamicode.com/c - 48;32     while ((c = getchar()) >= ‘0‘ && c <= ‘9‘)33         value = http://www.mamicode.com/value * 10 + c - 48;34     a = s * value;35 }36 const int maxn = 104;37 int arr[maxn];38 int n;39 int dp[maxn][maxn];40 int sum[maxn][maxn];41 42 int main() {43     //freopen("data.out", "w", stdout);44     //freopen("data.in", "r", stdin);45     //cin.sync_with_stdio(false);46     int T;47     cin >> T;48     for (int ii = 1; ii <= T; ++ii) {49         cin >> n;50         for (int i = 1; i <= n; ++i) scanf("%d", arr + i);51         Zero(dp);52         Zero(sum);53         for (int i = 1; i <= n; ++i) {54             int t = 0;55             for (int j = 0; j + i <= n; ++j) {56                 t += arr[i + j];57                 sum[i][i + j] = t;58             }59         }60         for (int j = 1; j <= n - 1; ++j) {61             for (int i = 1; i + j <= n; ++i) {62                 dp[i][i + j] = (1 << 31) - 1;63                 for (int k = 0; k <= j; ++k) {64                     dp[i][i + j] = min(dp[i][i + j], dp[i + 1][i + k] + k *arr[i] + dp[i + k + 1][i + j] +( k + 1) *sum[i + k + 1][i + j]);65                 }66             }67         }68         printf("Case #%d: ", ii);69         cout << dp[1][n] << endl;70     }71     return 0;72 }