首页 > 代码库 > 吹气球
吹气球
题目描述:
有n个气球,编号为0到n-1,每个气球都有一个分数,存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right],
left和right分别表示i气球相邻的两个气球。当i气球被吹爆后,其左右两气球即为相邻。要求吹爆所有气球,得到最多的分数。
注释:
(1) 你可以假设nums[-1] = nums[n] = 1
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:
给出[3, 1, 5, 8]
返回167
分析解答:
样例中[3,5,8],因先吹爆分数为3的气球只能得到两个数相乘的分数,先吹爆分数为5的气球可以得到3个数相乘更优。但是我们可以知道,对于8而言,
先吹3再吹5和先吹5再吹3,都是一样的因为8是最后吹。因为3和5的问题只在[3,5]区间内,跟区间外面没有关系。因此我们可以用区间dp去解决这个问题。
设dp[i][j]表示吹爆编号为 i 到 j 之间所有的气球所能得到的最大分数。如何转移?那么就穷举先吹爆的气球的编号k,但问题在于,先吹爆气球k会使得k-1号和k+1号气球相邻。所以最后吹爆k号气球,
这样dp方程就很好定义了dp[i][j] = dp[i][k-1] + score(k) + dp[k+1][j]。先吹区间[i,k-1]和区间[k+1,j]最后吹k。如果区间[i,k-1]或者[k+1,j]区间现在还不知道结果怎么办,我们可以用记忆化搜索的方式先去求解。
#include<bits/stdc++.h> using namespace std; int num[100],dp[100][100]; //记忆化搜索 int search(int a[],int l,int r) { if(dp[l][r]) return dp[l][r]; int ans=0; for(int k=l;k<=r;k++){ int mid=a[l-1]*a[k]*a[r+1]; int left=search(a,l,k-1); int right=search(a,k+1,r); ans=max(ans,left+mid+right); } dp[l][r]=ans; return dp[l][r]; } int main() { int n; while(scanf("%d",&n)){ memset(num,0,sizeof(num)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&num[i]); num[0]=1,num[n+1]=1; search(num,1,n); printf("%d",dp[1][n]); } }
吹气球
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。