【PTA】动态规划dp 7-1 矩阵链相乘问题 (20 分)
·
输入样例:
在这里给出一组输入。例如：
5
30 35 15 5 10 20
结尾无空行
输出样例:
在这里给出相应的输出。例如：
11875
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;
int p[MAX]={0};
int m[MAX][MAX];
int n;
int LookupChain(int i,int j)
{
if(m[i][j]>0) return m[i][j];
if(i==j) return 0;
m[i][j]=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];
for(int k=i+1;k<j;k++)
{
int t=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
}
}
return m[i][j];
}
int main()
{
cin>>n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
m[i][j] = 0;
for(int i=0; i<n+1; i++)
cin>>p[i];
cout<<LookupChain(1,n);
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
1
0- 0
已为社区贡献3条内容
所有评论(0)