POJ 1651 Multiplication Puzzle

POJ 1651 Multiplication Puzzle

题目描述：给你n个数，拿走一个数，会获得一个值，该值是这个数*它左边的数*它右边的数，最后的结果是取走中间n-2个数所获得的值的和。因为选取的顺序不一样，所获得的值也不一样，求取走中间n-2个值，最小的结果。 解题分析：其实就是类似矩阵连乘的思想，矩阵连乘中选取k作为最后一次乘法的中间矩阵，在这个题中选取第k个数作为最后一次乘法的中间数，那么问题转化为求区间[i,k]和区间[k,j]的最优解 + 这个乘积，状态转移方程就出来了： ans = min(ans,dp[i][k] + dp[k][j] + num[i]*num[k]*num[j]);像这种第一层循环是枚举长度的转移方法，还是记忆化搜索更好写。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 100 + 10;
int dp[maxn][maxn];
int num[maxn];
int n;int dfs(int u,int v)
{if(dp[u][v] > -1) return dp[u][v];if(v - u <= 1) return dp[u][v] = 0;int ans = INF;for(int i = u + 1; i <= v - 1; i++){ans = min(ans,dfs(u,i) + dfs(i,v) + num[u]*num[i]*num[v]);}return dp[u][v] = ans;
}int main()
{scanf("%d",&n);for(int i = 1; i <= n; i++){scanf("%d",&num[i]);}memset(dp,-1,sizeof(dp));dfs(1,n);printf("%d\n",dp[1][n]);return 0;
}

迭代的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 100 + 10;
int dp[maxn][maxn];
int num[maxn];
int n;int main()
{scanf("%d",&n);for(int i = 1; i <= n; i++){scanf("%d",&num[i]);}memset(dp,0,sizeof(dp));for(int l = 1; l <= n - 2; l++)//枚举中间元素的长度{for(int i = 1; i + l + 1<= n; i++)//枚举起点{int j = i + l + 1;//终点int ans = INF;for(int k = i + 1; k <= j -1; k++)//枚举中间元素，它的意思是最后一个选择的元素{ans = min(ans,dp[i][k] + dp[k][j] + num[i]*num[k]*num[j]);}dp[i][j] = ans;}}printf("%d\n",dp[1][n]);return 0;
}