好贷网好贷款

poj 1651 Multiplication Puzzle(区间DP,直接用矩阵相乘的方式也对)

发布时间:2016-12-3 3:57:53 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 1651 Multiplication Puzzle(区间DP,直接用矩阵相乘的方式也对)",主要涉及到poj 1651 Multiplication Puzzle(区间DP,直接用矩阵相乘的方式也对)方面的内容,对于poj 1651 Multiplication Puzzle(区间DP,直接用矩阵相乘的方式也对)感兴趣的同学可以参考一下。

1、http://poj.org/problem?id=1651 2、题目大意: 给出n个数,现在要将这些数一个一个的取出来,但是不能取出两个端点的数字,取出第i个数字(c[i])的代价是 c[i-1]*c[i]*c[i+1] 用矩阵相乘的思想dp[i][j]表示i到j区间取出来的代价 dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+c[i]*c[k]*c[j]) 3、AC代码: #include<stdio.h> #include<algorithm> using namespace std; #define N 105 #define INF 0x7ffffff int c[N]; int dp[N][N]; int main() { int n,tmp; while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=n;i++) dp[i][i]=0; for(int i=2;i<=n;i++) { for(int j=1;j+i<=n;j++) { dp[j][j+i]=INF; for(int k=j;k<i+j;k++) { dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k][j+i]+c[j]*c[k]*c[j+i]); } } } printf("%d\n",dp[1][n]); } return 0; } /* 5 10 1 50 20 5 */  

上一篇:Github学习总结
下一篇:ubuntu deb包管理

相关文章

相关评论