我们常见的石子合并问题一般就三种
第一种
n堆石子，每次合并的花费为两堆石子数目之和，求怎样合并可以使得合并为一整堆石子的总花费最少
实际上这就是HUfffman编码的变形，运用贪心策略，每次找出最小的两堆合并即可。
第二种
描述与第一种很相似，只不过每次合并只能合并相邻的两堆石子
那么贪心策略就不一定有用，局部最优的结果不一定是全局最优
那么我们就要考虑了，全局最优的子结构也应当是最优的。那么，我们就要考虑动态规划了，
状态转移方程：
dp[i][j] = min(dp[i][j],d[i][k]+dp[k+1][j]+sum[j]-sim[i])
解释一下，dp[i][j]表示合并第i堆到第j堆石子的最小花费，k的取值范围为i到j之间，表示分割点，例如1-3就可以分为1-2与3-3，sum【i】表示前i堆石子的总重量
初始化dp[i][i]为0，其他为无穷大
代码如下
#include<bits/stdc++.h>
using namespace std;
const int imax =0x7F7F7F7F;//极大值
int n;
int dp[2000][2000];//答案数组
int sum[2000];//花费数组
int data[2000];//数据数组
void init()//初始化
{
memset(sum,0,sizeof(sum));
memset(dp,imax,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>data[i];
sum[i]+=sum[i-1];
sum[i]+=data[i];
dp[i][i] = 0;
}
}
int solve()
{
init();
for(int v=1;v<n;v++)//v控制离中心线距离
{
for(int i=1;i<=n-v;i++)//i控制行
{
int j = i+v;//j控制列
int s = sum[j]-sum[i-1];//合并花费
for(int k=i;k<j;k++)
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+s);
}
}
return dp[1][n];
}
int main()
{
cout<<solve();
return 0;
}
上述代码的时间复杂度为O^3,那么我们有没有优化的方法呢？
平行四边形优化，我们用一个二维数组记录合并该堆石子的最佳决策点，也就是上述的K
有dp[i][j]的K值一定大于等于dp[i][j-1]的K,一定小于等于dp[i+1][j]的K
至于证明，感兴趣的同学可以去网上找一下大佬的解答，这里我就不误导大家了
下面给出优化后的代码
#include<bits/stdc++.h>
using namespace std;
const int imax =0x7F7F7F7F;//极大值
int n;
int dp[2000][2000];//答案数组
int sum[2000];//花费数组
int data[2000];//数据数组
int p[2000][2000];//优化数组
void init()//初始化
{
memset(sum,0,sizeof(sum));
memset(dp,imax,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>data[i];
sum[i]+=sum[i-1];
sum[i]+=data[i];
dp[i][i] = 0;
p[i][i] = i;
}
}
int solve()
{
init();
for(int v=1;v<n;v++)//v控制离中心线距离
{
for(int i=1;i<=n-v;i++)//i控制行
{
int j = i+v;//j控制列
for(int k=p[i][j-1];k<=p[i+1][j];k++){
int s = dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];//合并花费
if(dp[i][j]>s)
{
dp[i][j] = s;
p[i][j] = k;
}
}
}
}
return dp[1][n];
}
int main()
{
cout<<solve();
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// cout<<dp[i][j]<<" ";
// cout<<endl;
// }
return 0;
}
第三种：
环形
n堆石子围成环状，求解
那么我们的dp数组的含义就要进行改变了，dp[i][j]的意义以第i堆石子为起点，合并j堆石子的最小（大）花费
sum的含义为第i堆为起点，后j堆的总和
最终遍历dp[i][n]（1<=i<=n）
找到最小（大）的值
给一个oj题目让大家练手
贴出
给出ac代码
#include<bits/stdc++.h>
#define maxn 1<<27
#define N 101
using namespace std;
int n,ansmin = 1<<27,ansmax = -1;
int dp_max[N][N],dp_min[N][N];
int date[N];
void init()
{
cin>>n;
date[0] = 0;
for(int i=1;i<=n;i++)
{
cin>>date[i];
dp_min[i][1] = 0;//还没合并，没有花费
dp_max[i][1] = 0;
}
}
int sum(int i,int v)
{
int ans = 0;
for(;v>0;v--,i++)
{
if(i>n)
i%=n;
ans+=date[i];
}
return ans;
}
void AC()
{
init();
for(int v=2;v<=n;v++)//合并的个数
{
for(int i=1;i<=n;i++)//起始位置
{
dp_min[i][v] = maxn;
dp_max[i][v] = -1;
for(int k =1;k<v;k++)
{
dp_min[i][v] = min(dp_min[i][v],dp_min[i][k]+dp_min[(i+k-1)%n+1][v-k]+sum(i,v));
dp_max[i][v] = max(dp_max[i][v],dp_max[i][k]+dp_max[(i+k-1)%n+1][v-k]+sum(i,v));
}
}
}
for(int i=1;i<=n;i++)
{
if(dp_min[i][n]<ansmin)
ansmin = dp_min[i][n];
if(dp_max[i][n]>ansmax)
ansmax = dp_max[i][n];
}
}
int main()
{
AC();
cout<<ansmin<<endl<<ansmax;
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
