首页 > 试题广场 >

打气球的最大分数

[编程题]打气球的最大分数
  • 热度指数:2203 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个数组arr,长度为n。代表排有分数的气球。 每打爆一个气球都能获得分数,假设打爆气球的分数为X,获得分数的规则如下:
1)如果被打爆气球的左边有没被打爆的气球,找到离被打爆气球最近的气球,假设分数为L:如果被打爆气球的右边有没被打爆的气球,找到离被打爆气球最近的气球,假设分数为R.获得分数为L*X*R
2)如果被打爆的气球的左边有没被打爆的气球,找到离被打爆气球最近的气球,假设分数为L:如果被打爆气球的右边所有气球都已经被打爆,获得分数为L*X。
3)如果被打爆气球的左边所有的气球都已经被打爆:如果被打爆气球的右边有没被打爆的气球,找到离被打爆气球最近的气球。获得分数为X*R.
4)如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为X。
目标是打爆所有气球,获得每次打爆的分数。通过选择打爆气球的顺序,可以得到不同的总分,请返回能获得的最大分数。

输入描述:
输出包括两行,第一行包括一个整数n(0<=n<=500),第二行包括n个整数,代表数组arr (1<=arr[i]<=100)。


输出描述:
输出包括一个整数,代表可能获得的最大分数。
示例1

输入

3
3 2 5

输出

50

说明

2->1->3  3*2*5+3*5+5=50 
示例2

输入

8
23 4 45 65 23 43 54 56

输出

639019

备注:
时间复杂度,空间复杂度
头像 诗云panther
发表于 2021-08-18 13:53:01
include include using namespace std;typedef long long ll; const int MAXN = 210 * 2;const int SHIFT = 102;ll bit[MAXN]; void bitAdd(int x, int v) { 展开全文
头像 总之就是非常可爱
发表于 2022-02-14 18:46:06
//由左边的暴力递归版本改成动态规划的版本 #include<bits/stdc++.h> using namespace std; int main(){     int n;     cin>>n;     if 展开全文
头像 罗毅lala
发表于 2020-03-16 21:54:40
#include<iostream> #include<vector> #include<algorithm> using namespace std; //递归 //int Func(vector<int>& arr, int L, int 展开全文
头像 一个响亮的名字启动
发表于 2023-04-18 10:56:51
import sys n = int(input().strip()) arr = [1] + list(map(int, input().strip().split())) + [1] # TODO: dp def recur(l, r): if l == r: ret 展开全文

问题信息

上传者:小小
难度:
9条回答 6220浏览

热门推荐

通过挑战的用户

查看代码
打气球的最大分数