DP动态规划学习记录（五）——区间DP

石子合并（弱化版）

题目描述

设有 N(N≤300) 堆石子排成一排，其编号为 1,2,3,⋯,N。每堆石子有一定的质量 m i m_i mi​( m i m_i mi​≤1000)。现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

输入格式

第一行，一个整数 N。

第二行，N个整数 m i m_i mi​。

输出格式

输出文件仅一个整数，也就是最小代价。

输入输出样例

输入 #1

42 5 3 1

输出 #1

22

dp思路

1. 定义状态：$f[i][j]$表示区间$(i,j)$的最小合并价值
2. 分解子问题：f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] + s umi j ) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum_ij) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sumi​j)
3. 初始化状态数组和边界状态
   1. $f[][]=0x3f3f3f3f$
   2. $if(i==j)f[i][j]=0$
4. 计算顺序：从2堆开始算到第n堆（1堆不需要合并，所以代价为0）
5. 最终答案：$f[1][n]$

分解子问题中求$sum[i][j]$虽然不好求，但是我们可以用$sum[i]$表示从1到i的石子质量总和，用

#includeusing namespace std;int m[1005];int f[1005][1005];int sum[1005];int main(){int n;cin>>n;for(int i=1;i>m[i];//输入质量for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=0x3f3f3f3f;}//可以用memset(f,0x3f,sizeof(f))}//初始化sum[0]=0;for(int i=2;i<=n;i++){sum[i]=sum[i-1]+m[i];}//定义从1到i的石子重量for(int i=1;i<=n;i++)f[i][i]=0;//每个1堆不需要合并，所以代价直接定义为0for(int l=2;l<=n;l++){//从2堆开始，一直到n堆for(int i=1;i<=n-l+1;i++){//i枚举int j=i+l-1;//j为i加上数组长度-1for(int k=i;k<j;k++){//让k从i到k循环，依次比较，取合并最小值f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);}}}cout<<f[1][n];return 0;}

有点乱，优化一下结构：

最终dp代码

#includeusing namespace std;int f[1005][1005];int sum[1005];int main(){int n;cin>>n;    memset(f,0x3f,sizeof(f));    sum[0]=0;    f[0][0]=0;for(int i=1;i>a; sum[i]=sum[i-1]+a; f[i][i]=0;    }//初始化for(int i=1;i<=n;i++)f[i][i]=0;//每个1堆不需要合并，所以代价直接定义为0for(int l=2;l<=n;l++){//从2堆开始，一直到n堆for(int i=1;i<=n-l+1;i++){//i枚举int j=i+l-1;//j为i加上数组长度-1for(int k=i;k<j;k++){//让k从i到k循环，依次比较，取合并最小值f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);}}}cout<<f[1][n];return 0;}

题目描述

在一个圆形操场的四周摆放 N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 N 堆石子合并成1堆的最小得分和最大得分。

输入格式

数据的第1行是正整数 N，表示有 N堆石子。

第2行有 N个整数，第 i个整数 a i a_i ai​表示第 i 堆石子的个数。

输出格式

输出共2行，第1行为最小得分，第2行为最大得分。

输入输出样例

输入 #1

44 5 9 4

输出 #1

4354

说明/提示

1≤N≤100，0≤ a i a_i ai​≤20。

思路：

这道题和上道题的弱化版不太一样的是这道题的石子堆是围成圈的，意味着最后一堆石子和第一堆石子是相邻的。

虽然我们不能把它首尾相连，但是我们可以把两个一样的数组拼在一起，代码如下

#includeusing namespace std;int m[1005];int f[1005][1005];int f2[1005][1005];int sum[1005];int main(){int n;cin>>n;for(int i=1;i>m[i];m[i+n]=m[i];}memset(f,0x3f,sizeof(f));sum[0]=0;for(int i=1;i<=2*n;i++){sum[i]=sum[i-1]+m[i];}int h=2*n-1;for(int i=1;i<=h;i++){f[i][i]=0;f2[i][i]=0;}for(int l=2;l<=n;l++){for(int i=1;i<=h-l+1;i++){int j=i+l-1;for(int k=i;k<j;k++){f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);f2[i][j]=max(f[i][j],f2[i][k]+f2[k+1][j]+sum[j]-sum[i-1]);}}}int Min=1e19;int Max=0;for(int i=1;i<=n;i++){Max=max(Max,f2[i][i+n-1]);Min=min(Min,f[i][i+n-1]);}cout<<Min<<endl<<Max;return 0;}

2022.5.14

16：23

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖