(C++)戳西瓜
2024-09-08 01:29:35
写在前面的话:
请不要吝啬你的点赞!!!
题目描述
有 n 个西瓜,编号为0 到 n-1,每个西瓜上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的西瓜。每当你戳破一个西瓜 i 时,你可以获得 nums[left] *nums[i] *nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个西瓜的序号。注意当你戳破了西瓜 i 后,西瓜 left 和西瓜 right 就变成了相邻的西瓜。
求所能获得硬币的最大数量。
输入格式
共两行。
第一行:一个正整数n,代表西瓜个数。
第二行:共n个数字,每个数字表示西瓜上标的数字。
输出格式
一行,一个整数,获得硬币的最大数量。
样例
样例输入
4
3 1 5 8
样例输出
167
数据范围与提示
你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的西瓜,所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
思路
首先根据数据范围,我们可以推断
不是搜索,就是dp
然后我们再来看看。。。。
首先,我们分析一下题目,可以发现:
如果你戳破了第i个,那么会留下i-1和i+1,但是此时你的和却跟i-1,i,i+1都有关。
那么明显他是一个(i-1,i+1)的开区间;
但是题目却是要求把所有的气球给戳完,结合提示,我们就可以把题目改一下:
在一排气球中,请你戳破气球 0 和气球 n+1 之间的所有气球(不包括 0 和 n+1),
使得最终只剩下气球 0 和气球 n+1 两个气球,最多能够得到多少分?
设状态dp[i][j],表示戳破第i个到第j个的气球(因为是开区间,不包括i和j);
那么其实就转换为了求dp[0][n+1];
气球 i 和气球 j 之间的所有气球都可能是最后被戳破的那一个,不防假设最后戳破的为 k
现在我们就很好做了,对吧?
首先因为最后戳的是k所以要先把i到k的全部戳破,答案为dp[i][k];
然后k到j肯定也要戳完吧?答案为dp[k][j];
现在在气球i到气球j之间就只剩下i,k,j了,又因为i到k,k到j之间的所有气球全部被戳了,所以戳爆k的价值就是**nums[i]*nums[k]*nums[j]**啦!!!
所以这道题就出来啦!!!
#include<cstdio>
int dp[505][505];
int a[505];
int Max(int x,int y){
return x>y?x:y;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
a[0]=1;
a[n+1]=1;
for(int i=n;i>=0;i--){
for(int j=i+1;j<n+2;j++){
for(int k=i+1;k<j;k++){
dp[i][j]=Max(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
}
}
}
printf("%d",dp[0][n+1]);
return 0;
}
最新文章
- bootstrap在jsp中的应用
- VS2015 + OpenCV 2.4.X 配置环境
- hdu.5212.Code(莫比乌斯反演 &;&; 埃氏筛)
- OPENGL学习之路(0)--安装
- codevs1500 后缀排序
- eclipse设置字体、背景(豆绿)色、自动提示
- apache2: Could not reliably determine the server&#39;s fully qualified domain name
- cocos2d-x中的Jni使用(C++与Andriod方法互调)
- struts2的知识
- 使用vxsim(一)
- Firebird/InterBase内置函数使用说明
- STM32F10x 学习笔记5(USART实现串口通讯 1)
- Oracle_Q&;A_01
- Java基础笔记-String类2
- js 获取月份 格式yy-mm-dd
- HashMap/HashSet,hashCode,哈希表
- 本地电脑通过Navicat连接阿里云的Mysql数据库
- C# 不用递归,获取无限层级数据
- [py]资源搜集
- 【SQLSERVER学习笔记】分页存储过程+调用
热门文章
- [设计模式] 设计模式课程(十二)-- 门面模式(Facade)
- [刷题] PTA 03-树2 List Leaves
- [刷题] 70 Climbing Stairs
- python基础之python牛逼的设计模式
- Bootstrap Bootstrap3 与 Bootstrap4 的区别
- EasyUI_使用datagrid分页 (Day_28)
- VMware vRealize Suite 8.4 发布 - 多云环境的云计算管理解决方案
- 面试侃集合 | SynchronousQueue公平模式篇
- wangEditor 轻量级富文本框编辑器使用方法
- TVM优化Deep Learning GPU算子