acm有关问题

acm问题
http://acm.tju.edu.cn/toj/showp1759.html

原题联接

[解决办法]
一个动态规划解法:

#include <stdio.h>

#define MAXN 100

int n;
int num[MAXN+1];
int dp[MAXN+1][MAXN+1];

int search1(int i,int j)
{
int k,b;
if (dp[i][j]!=-1) return dp[i][j];


for (k=i+1; k<j; ++k)
{
b=search1(i,k)+search1(k,j)+num[i]*num[j]*num[k];
if (dp[i][j]==-1 || b<dp[i][j])
{
dp[i][j]=b;
}
}

return dp[i][j];
}

int main()
{
int i,j,k;
scanf("%d",&n);
for (i=1;i<=n ;++i ) scanf("%d",num+i);

for (i=1;i<=n ;++i ) 
for (j=1;j<=n ;++j ) dp[i][j]=-1; 

for (i=1;i<n-1 ;++i ) 
{
dp[i][i+1]=0;
dp[i][i+2]=num[i]*num[i+1]*num[i+2];
}
dp[n-1][n]=0;

printf("%d\n",search1(1,n));

return 0;
}