POJ 1651 区间DP Multiplication Puzzle

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 100 + 10;
 8 const int INF = 0x3f3f3f3f;
 9 
10 int n;
11 
12 int a[maxn];
13 int d[maxn][maxn];
14 
15 int DP(int i, int j)
16 {
17     if(j <= i + 1) return 0;
18     int& ans = d[i][j];
19     if(ans >= 0) return ans;
20     ans = INF;
21     int t = a[i] * a[j];
22     for(int k = i + 1; k < j; k++) ans = min(ans, DP(i, k) + DP(k, j) + t * a[k]);
23     return ans;
24 }
25 
26 int main()
27 {
28     while(scanf("%d", &n) == 1 && n)
29     {
30         for(int i = 0; i < n; i++) scanf("%d", a + i);
31         memset(d, -1, sizeof(d));
32         printf("%d\n", DP(0, n - 1));
33     }
34 
35     return 0;
36 }