POJ1651:乘法谜题挑战

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 int N;
 9 int dp[105][105],a[105];
10 
11 int main()
12 {   scanf("%d",&N);
13     for(int i=1;i<=N;i++) scanf("%d",&a[i]);
14     memset(dp,0,sizeof(dp));
15     for(int i=1;i1;i++) dp[i][i+2]=a[i]*a[i+1]*a[i+2];
16     for(int len=3;len){
17         for(int i=1;i<=N&&i+len<=N;i++){
18             int j=len+i;
19             for(int k=i+1;k){
20                 if(dp[i][j]==0) dp[i][j]=dp[i][k]+dp[k][j]+a[i]*a[k]*a[j];
21                 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
22             }
23         }
24     }
25     printf("%d\n",dp[1][N]);
26 }

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 typedef long long ll;
 7 
 8 const int INF=1000000000;
 9 
10 int N;
11 int dp[105][105],a[105];
12 
13 int main()
14 {   scanf("%d",&N);
15     for(int i=1;i<=N;i++) scanf("%d",&a[i]);
16     memset(dp,0,sizeof(dp));
17     for(int i=1;i1;i++) dp[i][i+2]=a[i]*a[i+1]*a[i+2];
18     for(int len=3;len){
19         for(int i=1;i<=N&&i+len<=N;i++){
20             int j=len+i;
21             dp[i][j]=INF;
22             for(int k=i;k1){
23                 int tem;
24                 if(k==i) tem=dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j];
25                 else tem=dp[i][k]+dp[k+1][j]+a[i]*a[k]*a[j];
26                 if(dp[i][j]>tem) dp[i][j]=tem; 
27             }
28         }
29     }
30     printf("%d\n",dp[1][N]);
31 }