神马品牌网痛击电影解析:求教一道PASCAL题目
来源：百度文库 编辑：神马品牌网 时间：2024/05/05 05:58:51
乘法游戏
【问题描述】
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第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。
【输入文件】
输入文件mul.in的第一行包括牌数(3<=n<=100)，第二行包括N个1-100的整数，用空格分开。
【输出文件】
输出文件mul.out只有一个数字：最小得分
【样例输入】
6
10 1 50 50 20 5
【样例输出】
3650
【时间限制】
1S
题目在上。最好能够比较详细的说明思路，方法。
【问题描述】
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第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。
【输入文件】
输入文件mul.in的第一行包括牌数(3<=n<=100)，第二行包括N个1-100的整数，用空格分开。
【输出文件】
输出文件mul.out只有一个数字：最小得分
【样例输入】
6
10 1 50 50 20 5
【样例输出】
3650
【时间限制】
1S
题目在上。最好能够比较详细的说明思路，方法。
本题要求一行牌的最佳合并方案，使得总得分最小。
本题可以用动态规划解决
参考程序
const maxn=101;
var a:array[1..maxn]of longint;
d:array[1..maxn,1..maxn]of longint;
min,j,k,n,i:longint;
begin
assign(input,'mul.in');reset(input);
assign(output,'mul.out');rewrite(output);
read(n);
for i:=1 to n do read(a[i]);{读入}
fillchar(d,sizeof(d),0);
for i:=2 to n do{赋初值}
d[i-1,i+1]:=a[i-1]*a[i]*a[i+1];
for k:=3 to n-1 do{动态规划}
for i:=1 to n-k do
begin
min:=maxlongint;
for j:=i+1 to i+k-1 do
if min>(d[i,j]+d[j,i+k]+a[i]*a[j]*a[i+k]) then
min:=(d[i,j]+d[j,i+k]+a[i]*a[j]*a[i+k]);
d[i,i+k]:=min;
end;
writeln(d[1,n]);{输出}
close(output);
end.
好难的样子 贫我目前的水平应该是每办法搞出来的
过几天帮你问问好了
等我的答复