石子归并实现及优化
想根据题来说一下式子归并的实现，分别是这三个题......
51Nod1021 ,51Nod1022 ,51Nod1023
我们看第一个题，就是最基本的链式石子归并，在链式石子归并中我们用dp[i][j]:表示从石头i到石头j我们要花费的最小代价，sum[i][j]表示从i到j石头的重量的和，这里就用到了区间dp的思想，我们在一个区间中枚举分别枚举长度，然后再这个某个长度下我们分隔区间，然后查找区间中的最小值，程序还是很好理解的
#include
#include
#include
#include
#include
#include
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N = 110;
int n,dp[N][N],a[N],sum[N];
int main()
{
scanf("%d",&n);
sum[0] = 0;
for(int i =1;
i <= n;
i ++)
scanf("%d",&a[i]);
for(int i =1;
i <= n;
i ++)
{
dp[i][i] = 0;
sum[i] = sum[i-1] + a[i];
}
for(int len = 2;
len <= n;
len ++)
{
for(int i = 1;
i <= n-len + 1;
i ++)
{
int j = i+len-1;
dp[i][j] = INF;
for(int k = i;
k < j;
k ++)
{
if(dp[i][j] > dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1])
dp[i][j] = dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1];
}
}
}
printf("%d\n",dp[1][n]);
return 0;
}
我们看第二题就转换成了环形石子归并问题，我们可以采取的一个解决方法是：我们将环形展开然后再添加一个重复的序列，我们从[1,n]区间中一次向后去n的长度，那么我们就可以近似的理解为是以每一个起点开始的式子归并，但是这样我们的时间复杂度就会是O(n^3)，这里我们就可以引入平行四边形优化，证明可以看：https://blog.csdn.net/lmyclever/article/details/6677683，以及大神的一篇论文：http://it.dgzx.net/drkt/oszt/zltk/yxlw/dongtai3.htm，这样我们就可以降低时间复杂度了
#include
#include
#include using namespace std;
const int INF = 999999999;
const int MAXN = 2010;
//平行四边形优化：
//状态转移方程；dp[i][j] = min(dp[i][j,]dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
//让dp[i][j]取最小值的K为K[i][j],则 K[i][j-1] <= K[i][j] <= K[i+1][j]int dp[MAXN][MAXN];
//由i开始到j最小的值是多少
int sum[MAXN];
int a[MAXN],s[MAXN][MAXN];
//s数组使用的是平行四边形优化，记录的是i~j之间最优状态的分割点int main() { //区间dp,石子归并问题
int n;
while(cin>>n) {
memset(s,0,sizeof(s));
memset(sum,0,sizeof(sum));
for(int i=1;
i<=n;
i++) {
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;
i<=n*2;
i++)
{
sum[i]=sum[i-1]+a[i];
s[i][i]=i;
//首先我们知道最小值肯定是他自身
dp[i][i]=0;
}
for(int len=2;
len<=n*2;
len++) { //枚举长度
for(int i=1,j=len;
j<=n*2;
i++,j++) { //i表示开始，j表示结束
dp[i][j]=INF;
for(int k=s[i][j-1];
k<=s[i+1][j];
k++)//意思也是枚举中间的节点信息
{
if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]
但是在第三题中，我们发现这里面的N太大了，开不出来二维数组，不能使用dp解决这个问题了，我们这里就会用到GarsiaWachs算法，要是了解这个算法的我觉得重点就是边界的判断上了，程序来自：https://blog.csdn.net/acdreamers/article/details/18043897
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
const int N = 51000;
ll a[N],n;
ll ans,t;
void Print(int t)
{
for(int i = 0;
i < t;
i ++)
cout< 0 && a[j-1] < temp;
j --)
a[j] = a[j-1];
a[j] = temp;
//print(t);
while( j >= 2 && a[j] >= a[j-2])
{
int d = t - j;
combine(j-1);
j = t -d;
}
}int main()
{
//寻找a[k-1] <= a[k+1],然后将a[k-1],a[k]合并，最终向前找一个最大的j满足a[j] > a[k] + a[k-1],将合并的数插到j位置的后面
scanf("%I64d",&n);
for(int i = 0;
i < n;
i ++)
scanf("%d",&a[i]);
ans = 0;
t = 1;
//最后只会剩一个数，我们要保留这样的一个数
for(int i = 1;
i = 3 && a[t-3] <= a[t-1]) //找到了三个数中的第三个位置
combine(t-2);
}
while(t > 1) combine(t-1);
printf("%I64d\n",ans);
return 0;
}
【石子归并实现及优化】
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- MybatisPlus使用queryWrapper如何实现复杂查询
- python学习之|python学习之 实现QQ自动发送消息
- 孩子不是实现父母欲望的工具——林哈夫
- opencv|opencv C++模板匹配的简单实现
- Node.js中readline模块实现终端输入
- java中如何实现重建二叉树
- 人脸识别|【人脸识别系列】| 实现自动化妆
- paddle|动手从头实现LSTM
- pytorch|使用pytorch从头实现多层LSTM