51nod 1023 石子归并 V3

本文主要是介绍51nod 1023 石子归并 V3，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1023&judgeId=542658

叫做：GarsiaWachs算法
就是加入有$a,b,c$三个先合并左边两个的代价是$2a+ab+c$，而先合并右边两个的代价是$a+2b+2c$，所以只用看$a$和$c$，$a<c$就先合并左边两个
于是先合并$a<c$的吧，完了之后如果还有剩就从右边开始合并$bc$
合并$ab$的时候，合并之后的插入从左边数第一个大于他的数的后面，为什么我也不怎么理解。。。

然后就是如果这道题就这样按照所说的弄的话会$TLE$，因为插入删除都是$O(n)$的，所以想了个办法让这个$n$变得比较小
所以新开了一个数组，一个一个加石头进去，满足$ab$的合并条件就合并，这样会保持$n$比较小

而函数里面递归那里，就是让$i$减小的，假如现在那个位置距离末尾差了$d$个，而处理又是在当前位置前面，所以处理完之后还是应该差$d$个才对

#include"bits/stdc++.h"
using namespace std;
const int maxn=5e5+5;
long long N,CNT;
long long sum;
int a[maxn];
vector<int>stone;
void combine(int k)
{int tp=stone[k]+stone[k-1];sum+=tp;stone.erase(stone.begin()+k);stone.erase(stone.begin()+k-1);int i=0;for(i=k-2; i>=0; i--){if(stone[i]>tp){stone.insert(stone.begin()+i+1,tp);break;}}CNT--;i++;//因为又加了一个进去while(i>=3&&stone[i-2]<=stone[i]){int d = CNT - i;//当前位置处理前离末尾差d个combine(i-1);i = CNT - d;//处理后也应该差d个才对}
}
int main()
{while(cin>>N){stone.clear();stone.push_back(1e9);sum=0;for(int i=1; i<=N; i++)cin>>a[i];CNT=0;for(int i=1; i<=N; i++){stone.push_back(a[i]);CNT++;while(CNT>=3&&stone[CNT-2]<=stone[CNT])combine(CNT-1);//合并左边的}while(CNT>1)combine(CNT);//左边的合并完了，合并右边的cout<<sum<<"\n";}
}

贴一个$dp$的：

#include"iostream"
#include"string.h"
using namespace std;
const int maxn=1e2+5;
int dp[maxn][maxn],a[maxn],sum[maxn];
int N;
int main()
{while(cin>>N){memset(dp,0x3f,sizeof(dp));memset(sum,0,sizeof(sum));for(int i=1;i<=N;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];for(int i=0;i<=N;i++)dp[i][i]=0;for(int n=2;n<=N;n++){for(int i=1;i<=N-n+1;i++){int j=i+n-1;for(int k=1;k<=j;k++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);}}}cout<<dp[1][N]<<"\n";}
}

这篇关于51nod 1023 石子归并 V3的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---