乘法游戏

news/2024/10/30 19:50:21/

【题目描述】

桌子上从左到右放着n张牌,每张牌上都有一个正整数。每次,我们可以从中拿出一张牌(不能拿第一张和最后一张牌),得分就是这张牌的数乘以他左边和右边的数。如此不断的重复,最后就只剩下两张牌了。现在,你的目标就是使得分的和最小。
    例如,如果数是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的整数,用空格分开。

【输出格式】

输出文件只有一个数字:最小得分

【分析】

区间dp,状态:f[i][j]表示[i,j]区间内的最小分数。

我们在区间内枚举一个k,表示取的那个数,就可以解出f[i][j]=min(f[i][k]+a[i]*a[k]*a[j]+f[k][j])

答案就是f[1][n],初始值,所有的都是inf,f[i][i]=0,f[i-1][i]=0,f[i][i+1]=0。

【代码】

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int inf=9999999;
 5 int f[110][110],n,a[110];
 6 int main()
 7 {
 8     memset(f,inf,sizeof(f));
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++){
11         scanf("%d",&a[i]);
12         f[i-1][i]=0,f[i][i]=0,f[i][i+1]=0;
13     }
14     for(int i=2;i<=n-2;i++) f[i-1][i+1]=a[i-1]*a[i]*a[i+1];
15     for(int i=n-2;i>=1;i--){
16         for(int j=i+2;j<=n;j++){
17             for(int k=i+1;k<j;k++){
18                 f[i][j]=min(f[i][j],f[i][k]+a[i]*a[k]*a[j]+f[k][j]);
19             }
20         }
21     }
22     printf("%d\n",f[1][n]);
23     return 0;
24 }

 

转载于:https://www.cnblogs.com/Dawn-Star/p/9153119.html


http://www.ppmy.cn/news/325600.html

相关文章

HTML的游戏分数怎么设置,HTML5《拯救分号》游戏

JavaScript 语言&#xff1a; JaveScriptBabelCoffeeScript 确定 $.key { left: 0, right: 0, up: 0, space: 0 } $.offset { x: 0, y: 0 } $.dt 0; $.lt 0; $.elapsed 0; $.mute 0; $.glitch 0; $.canEdit false; $.ios /iPad|iPhone|iPod/.test(navigator.userAgent…

Java实现王者荣耀小游戏(简单版,带有图片资源)

这周是实践周&#xff0c;要写期末大作业。参考视频&#xff0c;我写了王者荣耀小游戏&#xff0c;功能比较简单&#xff0c;但是即使简单我也遇到了很多Bug&#xff0c;开心的是最后做出来了。 多说不易&#xff01;看下面代码。 本设计所开发实现的是基于Java的一个王者荣耀…

1150. 【克罗地亚】NIKOLA (Standard IO)

题目描述 Nikola现在已经成为一个游戏里的重要人物。这个游戏是由一行N个方格&#xff0c;N个方格用1到N的数字表示。Nikola开始是在1号位置&#xff0c;然后能够跳到其他的位置&#xff0c;Nikola的第一跳必须跳到2号位置。随后的每一跳必须满足两个条件&#xff1a; 1、如果…

BZOJ 1150 数据备份

https://cn.vjudge.net/problem/HYSBZ-1150 题目 你在一家 IT 公司为大型写字楼或办公楼&#xff08;offices&#xff09;的计算机数据做备份。然而数据备份的工作是枯燥乏味的&#xff0c;因此你想设计一个系统让不同的办公楼彼此之间互相备份&#xff0c;而你则坐在家中尽享计…

【游戏程序设计】三维游戏示例-战术竞技游戏Demo(二)

突然相遇&#xff1a; 然后死掉. 源代码以及实现方法&#xff1a; 首先定义一个Character类为角色的基类&#xff0c;然后英雄魔兽(战士)类Warcraft与托尼(法师)类Timy继承于它。分别实现对应的方法。 角色类有许多的方法&#xff0c;也有一些需要子类实现的虚函数方法。 Ch…

用easyx图形库做一个简单的c++小游戏---障碍跑酷(还有难度等级)

用easyx图形库做一个简单的c小游戏—障碍跑酷 开发环境&#xff1a;visual c6.0 库&#xff1a;easyx图形库 下载地址>>> (https://easyx.cn/downloads/) 当时我原本是想模仿做一个Flappy Bird的小游戏&#xff0c;在想如何写的时候突然有了新的想法&#xff0c;就有…

python设计拼图游戏tkinter_tkinter做一个拼图游戏

今天我们利用canvas绘制、删除图片的的函数&#xff0c;以及鼠标事件的绑定来制作一个简单的九宫格拼图游戏。 首先从网上下九张图&#xff0c;它们是把一张图分割成了九宫图&#xff0c;打乱后显示在canvas画布上。 接下来我们只要实现图片的选中与拖动即可&#xff0c;用到了…

c语言跑酷游戏,C++用easyx图形库实现障碍跑酷小游戏

用easyx图形库做一个简单的c++小游戏—障碍跑酷 开发环境:visual c++6.0 库:easyx图形库 下载地址 当时我原本是想模仿做一个Flappy Bird的小游戏,在想如何写的时候突然有了新的想法,就有了这个障碍跑酷的小游戏。(这是我之前写的代码,没有很注重规范,看上去有点乱,但我…