POJ1651Multiplication Puzzle（区间DP）

比较好做的区间DP

状态转移方程：DP[i][j] 表示区间[i,j]最小的乘积和。

DP[i][j] = MIN{DP[i][k-1]+DP[k+1][j] + a[k]*a[i-1]*a[j+1] | i<k<j};

最后结果就是DP[2][N-1]

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define eps 1e-15
16 #define MAXN 105
17 #define INF 1000000007
18 #define MAX(a,b) (a > b ? a : b)
19 #define MIN(a,b) (a < b ? a : b)
20 #define mem(a) memset(a,0,sizeof(a))
21 
22 int a[105],DP[105][105],N;
23 
24 int main()
25 {
26     while(~scanf("%d", &N))
27     {
28         for(int i=0;i<=N;i++)
29         {
30             for(int j=0;j<=N;j++) DP[i][j] = INF;
31         }
32         for(int i=1;i<=N;i++)
33         {
34             scanf("%d", &a[i]);
35         }
36         for(int i=2;i<N;i++)
37         {
38             for(int j=i;j>=2;j--)
39             {
40                 if(i == j) DP[j][i] = a[i] * a[i-1] * a[i+1];
41                 else
42                 {
43                     int x = DP[j+1][i]+a[j]*a[j-1]*a[i+1];
44                     int y = DP[j][i-1]+a[i]*a[j-1]*a[i+1];
45                     DP[j][i] = MIN(x, y);
46                     if(i-j>1)for(int k = j+1;k<i;k++)
47                     {
48                         x = DP[j][k-1] + DP[k+1][i] + a[k]*a[j-1]*a[i+1];
49                         DP[j][i] = MIN(DP[j][i], x);
50                     }
51                 }
52             }
53         }
54         printf("%d
", DP[2][N-1]);
55     }
56     return 0;
57 }