乘法游戏题解

题目描述

乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第1张和最后1张牌。最后一次移动后，这里只剩下两张牌。
你的目标是使得分的和最小。
例如，如果数是10 1 50 20 5，依次拿1、20、50，总分是 10150+50205+10505=8000
而拿50、20、1，总分是15020+1205+1015=1150。

题解

列举左端点i和右端点j中枚举断点k，则
dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
解释：dp[i][j]表示(i,j)内的最优解。对于后半句，有：当前最大值等于：（断点前的结果+断点后的结果+取出断点处应添加的答案）。
则有两种实现方法：

1、dfs+记忆化搜索

不解释哩！记得写记忆化！

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e2 + 5;
int dp[N][N],n,a[N];
int dfs(int L,int R){
	if(L == R - 1)return 0;
	if(dp[L][R] != -1)return dp[L][R];
	dp[L][R] = INF;
	for(int i = L + 1 ; i < R ; i ++)
		dp[L][R] = min(dp[L][R],dfs(L,i) + dfs(i,R) + a[i] * a[L] * a[R]);
	return dp[L][R];
}
signed main(){
	scanf("%d",&n);
	memset(dp,-1,sizeof(dp));
	for(int i = 1 ; i <= n ; i ++)
		scanf("%d",&a[i]),dp[i][i+1] = 0;
	dfs(1,n);
	printf("%d",dp[1][n]);
	return 0;
}

2、纯递推！！

枚举区间的长度，再枚举起点，则终点可确定。再次枚举断点，进行计算。
不能写枚举ijk的原因是，当j++的时候，dp[k][j]的值尚未更新，导致每次得到的不是局部最优解！！//这里想了好长时间

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f , N = 1e2 + 5;
int dp[N][N],n,a[N];
signed main(){
	scanf("%d",&n);
	memset(dp,0x3f,sizeof(dp));
	for(int i = 1 ; i <= n ; i ++)
		scanf("%d",&a[i]),dp[i][i+1] = 0;
	for(int l = 3 ; l <= n ; l ++)
		for(int i = 1 ; i + l - 1 <= n ; i ++){
			int j = i + l - 1;
			for(int k = i + 1 ; k < j ; k ++)
				dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);

		}
	printf("%d",dp[1][n]);
	return 0;
}