首页 > 代码库 > 区间DP-POJ1651-Multiplication Puzzle
区间DP-POJ1651-Multiplication Puzzle
题目：http://poj.org/problem?id=1651
水题
题意：若干张卡片，第i张卡片的分值为a[ i ] ( 1 <= i <= N )。现在游戏如下，给定N张卡片，除了第一张和最后一张卡片不可取之外，你可任取一张，得到分值a[ i – 1] * a[ i ] * a[ i + 1 ]，然后就把这张卡片去掉。题目要求最后计算最小的总得分。
原理：矩阵连乘。
1 #include <iostream> 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<string.h> 5 using namespace std; 6 long long dp[110][110],a[110],tmp; 7 8 int main() 9 {10 int n,i,j,k,t,len,m,tmp;11 while(scanf("%d",&n)!=EOF)12 {13 for(i=0; i<n; i++)14 scanf("%d",&a[i]);15 memset(dp,0,sizeof(dp));16 for(len=1; len<=n-1; len++)17 for(i=1,j=len+1; j<=n-1; i++,j++)18 {19 m=999999999;20 for(k=i;k<=j-1;k++)21 {22 tmp=dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];23 if(tmp<m)24 m=tmp;25 }26 d[i][j]=m;27 }28 printf("%lld\n",dp[0][n-1]);29 }30 return 0;31 }
区间DP-POJ1651-Multiplication Puzzle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。