欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

acwing.【合并石子】(区间dp)

时间:2023-04-26

贪心是局部最优解,只能保证局部最优,不能保证全局最优,不能用贪心做。

思路:最后一次合并一定是两堆最小合并代价+所有石子的代价,这两堆是[1,k][k+1,n],k可能是1~n中的任意一个数,假设我们知道k是多少,那么,问题转化成求[1,k]和[k+1,n]的最小合并代价,.......当石子剩余2时,递推回去就可求解了。但是,还有一个问题,去选出k,我们可以遍历当前所求区间每一种k的取值,然后选出最小值。

以我目前菜鸡的理解水平,dp就是上述内容倒着看,我们先求出所有递归的结束条件,然后再去求上一层......。但是与递归最大的差别就是不会求重复数据,这样就会降低时间复杂度。

#include#includeusing namespace std;int arr[310];int dp[310][310];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>arr[i]; arr[i]=arr[i-1]+arr[i];}for(int len=2;len<=n;len++){for(int i=1;i<=n-len+1;i++){int mo=i+len-1;dp[i][mo]=1e8;for(int k=i;k

若有问题,请各位大佬积极指正。

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。