首页 > 代码库 > tyvj1014 - 乘法游戏

tyvj1014 - 乘法游戏

2024-07-29 12:17:55   217人阅读

题目链接：https://www.tyvj.cn/Problem_Show.aspx?id=1014

背景 Background
太原成成中学第2次模拟赛 第四道
描述 Description
乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第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。
输入格式 Input Format
输入文件mul.in的第一行包括牌数(3<=n<=100)，第二行包括N个1-100的整数，用空格分开。
输出格式 Output Format
输出文件mul.out只有一个数字：最小得分
样例输入 Sample Input

样例输出 Sample Output

时间限制 Time Limitation
各个测试点1s

[分析]

记忆化搜索DP

f[i][j]表示区间［i，j］所得到的最小值。F[I,J]:=MIN(F[I,K]+F[K,J]+A[I]*A[K]*A[J])其中I<K<J。（K表示区间[i,j]最后一次取第K张牌）

不断地划分区间，把结果保存起来。

#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;long long int f[101][101];int a[101], i, j, n, INF=0x7f7f7f7f;void dfs(int l, int r) {    if(r-l<=1) {f[l][r]=0; return;} if(f[l][r]!=INF) return;    for(int i=l+1;i<=r-1;++i) dfs(1,i),dfs(i,r),f[l][r]=min(f[l][r],f[l][i]+f[i][r]+a[i]*a[l]*a[r]);}int main(void) {    freopen("in1.txt","r",stdin);    scanf("%d",&n);for(i=1;i<=n;scanf("%d",a+i++))        ;for(i=0;i<=n;++i)for(j=0;j<=n;++j)f[i][j]=INF;dfs(1,n);printf("%lld\n",f[1][n]);    return 0;}

或者：

 1 var 2  i,j,k,l,n:longint;  3  f:array[1..100,1..100]of longint; 4  num:array[1..100]of longint; 5  6  7 begin 8   readln(n); 9   for i:=1 to n do10    read(num[i]);11 12     for l:=1 to n do13       for i:=1 to n-l+1 do14         begin15           j:=i+l+1;16           f[i,j]:=MaxLongint;17           for k:=i+1 to j-1 do18             if f[i,k]+f[k,j]+num[i]*num[k]*num[j]<f[i,j] then19               f[i,j]:=f[i,k]+f[k,j]+num[i]*num[k]*num[j];20         end;21         22   writeln(f[1,n]);23   24 end.

 

tyvj1014 - 乘法游戏


联系
我们