所谓区间dp，指在一段区间上进行动态规划，一般做法是由长度较小的区间往长度较大的区间进行递推，最终得到整个区间的答案，而边界就是长度为1以及2的区间。
转移方程
区间dp常见的转移方程如下：
1
| dp(i,j) = min{dp(i,k-1) + dp(k,j)} + w(i,j) (i < k <= j)
|
其中dp(i,j)表示在区间[i,j]上的最优值，w(i,j)表示在转移时需要额外付出的代价，min也可以是max。
四边形不等式
按上述转移方程递推的时间复杂度为O(n3)，如果w函数满足区间单调性和四边形不等式，可通过四边形不等式将时间优化到O(n2)。
- 区间单调性：对于
a<=b<=c<=d，有w(b,c) <= w(a,d)。
- 四边形不等式：对于
a<=b<=c<=d，有f[a][c]+f[b][d]<=f[a][d]+f[b][c]
当w满足以上两点时，dp也满足四边形不等式，定义s(i,j)表示dp(i,j)取得最优值时对应的下标，那么有s(i,j)单调，即s(i,j)<=s(i,j+1)<=s(i+1,j)。
将该单调性应用到转移方程中，可大大缩小k的枚举范围。
1
| dp(i,j) = min{dp(i,k-1) + dp(k,j)} + w(i,j) (s(i,j-1) <= k <= s(i+1,j))
|
石头合并
我们常见的石子合并问题一般就三种
第一种
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，其他为无穷大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #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）
找到最小（大）的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #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;
}
|
请我一杯咖啡吧！
微信打赏