推广营销海外网站,做一个网站需要多长时间,赣州seo优化,有没有专业做挂的网站吗题目描述
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中#xff0c;玩家拿出一张牌#xff0c;得分是用它的数字乘以它左边和右边的数#xff0c;所以不允许拿第1张和最后1张牌。最后一次移动后#xff0c;这里只剩下两张牌。 你的目标是使得分的…题目描述
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中玩家拿出一张牌得分是用它的数字乘以它左边和右边的数所以不允许拿第1张和最后1张牌。最后一次移动后这里只剩下两张牌。 你的目标是使得分的和最小。
解析
区间dp 定义dp[i][j]是把i j 之间所有数去掉的代价最小值 那么显然
if(ji1) return 0;而当ij中有数时我们可以枚举i j之间取的最后一个数的位置k 显然: ikj 那么这个过程就是把i k之间的书都取完再把k j之间的数取完最后取k代价是a[k]*a[i]*a[j]) 那么转移方程就是
dp[i][j]min(dp[i][j],dfs(i,k)dfs(k,j)a[i]*a[j]*a[k]);枚举k的位置取min即可 注意要使用记忆化搜索优化时间复杂度
代码
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N150;
int m,n;
int dp[N][N],a[N];
int dfs(int i,int j){if(dp[i][j]) return dp[i][j];if(ji1) return 0;dp[i][j]2e9;for(int ki1;kj;k){dp[i][j]min(dp[i][j],dfs(i,k)dfs(k,j)a[i]*a[j]*a[k]);}return dp[i][j];
}
int main(){scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);printf(%d,dfs(1,n));
}
/*
6
10 1 50 50 20 5
*/法2
递推 思路是类似的从小到大枚举区间长度以保证 用到的dp都已更新完即可 时间复杂度n^3
代码
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N150;
int m,n;
int dp[N][N],a[N];
int main(){scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);for(int l3;ln;l){for(int i1;il-1n;i){int jil-1;dp[i][j]2e9;for(int ki1;kj;k){dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]a[k]*a[i]*a[j]);}}}printf(%d,dp[1][n]);
}
/*
6
10 1 50 50 20 5
*/thanks for reading!
