POJ 1651 Multiplication Puzzle(区间DP)

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<string>
 5 #include<stdlib.h>
 6 #include<algorithm>
 7 using namespace std;
 8 int dp[110][110];
 9 int a[110];
10 const int INF=0x3f3f3f3f;
11 int main()
12 {
13     int i,j,k,p,n=0;
14     while(scanf("%d",&n)!=EOF)
15     {
16         for(i=0;i<n;i++)
17             scanf("%d",&a[i]);
18         memset(dp,0,sizeof(dp));
19         for(p=3;p<=n;p++)           //区间长度
20         {
21             for(i=0;i<n-2;i++)      //枚举区间起点
22             {
23                 j=i+p-1;            //区间终点
24                 dp[i][j]=INF;
25                 for(k=i+1;k<j;k++)
26                     dp[i][j]=min(dp[i][k]+dp[k][j]+a[i]*a[k]*a[j],dp[i][j]);
27             }
28         }
29         printf("%d\n",dp[0][n-1]);
30     }
31     return 0;
32 }