首页 > 代码库 > tyvj1014 乘法游戏
tyvj1014 乘法游戏
描述
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中,玩家拿出一张牌,得分是用它的数字乘以它左边和右边的数,所以不允许拿第1张和最后1张牌。最后一次移动后,这里只剩下两张牌。
你的目标是使得分的和最小。
例如,如果数是10 1 50 20 5,依次拿1、20、50,总分是 10*1*50+50*20*5+10*50*5=8000
而拿50、20、1,总分是1*50*20+1*20*5+10*1*5=1150。
你的目标是使得分的和最小。
例如,如果数是10 1 50 20 5,依次拿1、20、50,总分是 10*1*50+50*20*5+10*50*5=8000
而拿50、20、1,总分是1*50*20+1*20*5+10*1*5=1150。
输入格式
输入文件的第一行包括牌数(3<=n<=100),第二行包括N个1-100的整数,用空格分开。
输出格式
输出文件只有一个数字:最小得分
测试样例1
输入
6
10 1 50 50 20 5
输出
3650
/*枚举区间内最后一个乘数*/#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#define ll long longusing namespace std;const int maxn = 125;const ll inf = 987654321234LL;ll read(){ char ch=getchar(); ll x=0,f=1; while(!(ch>=‘0‘&&ch<=‘9‘)){if(ch==‘-‘)f=-1;ch=getchar();}; while(ch>=‘0‘&&ch<=‘9‘){x=x*10+(ch-‘0‘);ch=getchar();}; return x*f;}int n;ll a[maxn],dp[maxn][maxn];int main(){ n = read(); for(int i = 1;i <= n;i++) a[i] = read(); for(int i = 0;i <= n;i++){ for(int j = 0;j <= n;j++){ dp[i][j] = inf; } } for(int i = 1;i < n;i++){ dp[i][i+1] = 0; } int j; for(int l = 3;l <= n;l++){ for(int i = 1;i <= n-l+1;i++){ j = i + l - 1; for(int k = i + 1;k <= j-1;k++){ dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j] + a[i]*a[k]*a[j]); } } } cout<<dp[1][n]; return 0;}
tyvj1014 乘法游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。