石子合并+环形石子合并+能量项链+凸多边形的划分——区间DP

一、石子合并 (经典例题)

设有 N 堆石子排成一排，其编号为 1,2,3,…,N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入
第一行一个数 N 表示石子的堆数 N (1 ≤ N ≤ 300)。
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。

输出
输出一个整数，表示最小代价。

Input
4
1 3 5 2

Output
22
解析：
用一个状态表示一个区间，f[i][j] 表示将第 i 堆石子到第 j 堆石子合并成一堆石子的合并方式的集合。
状态转移：
例如，将 区间 [i,j] 分为 [i,k] 和 [k+1,j] ，枚举 k 在区间[i,j]的位置就能找到最小代价使得 合并这两个区间的代价最小，即 f[i][k]+f[k+1,j] 的值最小，再加上一个第 i 堆到第 j 堆的总重量即可。
因为在计算状态的时候，得保证在这个状态之前的状态已经计算完毕，所以可以采用循环区间长度从小到大的方式，进行计算。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=310;
int n;
int s[N];
int f[N][N];
void solve()
{cin>>n;for (int i=1;i<=n;i++) cin>>s[i];for (int i=1;i<=n;i++) s[i] +=s[i-1];for (int len=1;len<=n;len++)for (int i=1;i+len-1<=n;i++){int l=i,r=i+len-1;if(len!=1) f[l][r]=2e9;                             //因为当len=1时，只有一堆石子，不需要合并，代价为0for (int k=l;k<r;k++)f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);}cout<<f[1][n];
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}

 

二、 环形石子合并 (加个环)

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：
选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

输入
第一行包含整数 n (1 ≤ n ≤ 200)，表示共有 n 堆石子。
第二行包含 n 个整数，分别表示每堆石子的数量。

输出
共两行，第一行为合并得分总和最小值，第二行为合并得分总和最大值。

Input
4
4 5 9 4

Output
43
54

解析：
与上一题的石子合并的想法基本相似，不同的是这道题的石堆的摆放方式是环式的。
在上道题的基础上，将这个环断开，变成一条链，枚举每个断点。
不过直接枚举的话，时间复杂度是 n^4，超时了。
我们可以将数组读入，再将数组复制一遍，再接到这个数组上。
这样时间复杂度就降下来了，时间复杂度在 n^3。
注意：在做这种环式的题，就可以多想一想这样的方法

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=410;
int n;
int a[N],s[N];
int f[N][N],g[N][N];
void solve()
{cin>>n;for (int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];for (int i=1;i<=2*n;i++) s[i]=s[i-1]+a[i];for (int len=1;len<=n;len++)                //一层循环枚举区间长度for (int i=1;i+len-1<=2*n;i++)              //二层循环枚举区间的左右端点{int l=i,r=i+len-1;if (len!=1) f[l][r]=2e9,g[l][r]=-2e9;for (int k=l;k<r;k++)                   //状态转移{f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+s[r]-s[l-1]);}}int minx=2e9,maxx=-2e9;                     //找到最小值，最大值for (int i=1;i<=n;i++) {minx=min(minx,f[i][i+n-1]);maxx=max(maxx,g[i][i+n-1]);}cout<<minx<<endl<<maxx<<endl;
}
signed main()
{ios;int T=1;//cin>>T;while (T--) solve();return 0;
}

三、能量项链 (跟上个题一样)

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链，在项链上有 N 颗能量珠。
能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。
并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。
因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。

如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为 m×r×n（Mars 单位），新产生的珠子的头标记为 m，尾标记为 n。
需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。
显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设 N=4，4 颗珠子的头标记与尾标记依次为 (2，3)(3，5)(5，10)(10，2)。
我们用记号 ⊕ 表示两颗珠子的聚合操作，(j⊕k) 表示第 j，k 两颗珠子聚合后所释放的能量。则
第 4、1 两颗珠子聚合后释放的能量为：(4⊕1)=10×2×3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710。

输入
输入的第一行是一个正整数 N (4 ≤ N ≤ 100)，表示项链上珠子的个数。
第二行是 N 个用空格隔开的正整数，所有的数均不超过 1000，第 i 个数为第 i 颗珠子的头标记，当 i<N 时，第 i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记，第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出
输出只有一行，是一个正整数 E (1 ≤ E ≤ 2e9)，为一个最优聚合顺序所释放的总能量。

Input
4
2 3 5 10

Output
710

解析：
跟上一题一样，纯套路。

//代码一:开个结构体存储头和尾，相当于一个点，就跟上道题一模一样了
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=400;
struct node
{int x,y;
}str[N];
int n;
int a[N];
int f[N][N];
void solve()
{cin>>n;for (int i=1;i<=n;i++) cin>>a[i];for (int i=1;i<=n;i++){if (i==1)  str[i]={a[n],a[i]};else str[i]={a[i-1],a[i]};str[i+n]=str[i];}for (int len=1;len<=n;len++)for (int i=1;i+len-1<=2*n;i++){int l=i,r=i+len-1;if (len!=1) f[l][r]=-2e9;for (int k=l;k<r;k++){f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+str[l].x*str[k].y*str[r].y);          //左区间左端点的头*左区间右端点的尾*右区间右端点的尾}}int ans=-2e9;for (int i=1;i<=n;i++) ans=max(ans,f[i][i+n-1]);cout<<ans;
}
signed main()
{ios;int T=1;//cin>>T; while (T--) solve();return 0;
}//代码二
//划分方式:f(l,r)=f(l,k)+f(k,r)+a[l]*a[k]*a[r]
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=400;
int n;
int a[N];
int f[N][N];
void solve()
{cin>>n;for (int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];for (int len=3;len<=n+1;len++)                      //至少 3 个点for (int i=1;i+len-1<=2*n;i++){int l=i,r=i+len-1;f[l][r]=-2e9;for (int k=l;k<r;k++){f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]); }}int ans=-2e9;for (int i=1;i<=n;i++) ans=max(ans,f[i][i+n]);      //查找区间长度为 n+1 的cout<<ans;
}
signed main()
{ios;int T=1;//cin>>T; while (T--) solve();return 0;
}

 四、凸多边形的划分

给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。
将这个凸多边形划分成 N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

输入
第一行包含整数 N (N ≤ 50)，表示顶点数量。
第二行包含 N 个整数，依次为顶点 1 至顶点 N 的权值。

输出
输出仅一行，为所有三角形的顶点权值乘积之和的最小值。
数据保证所有顶点的权值都小于 1e9

Input
5
121 122 123 245 231

Output
12214884

 解析：

f[l][r] 表示 所有 由(l,l+1)(l+1,l+2)……(r-1,r)(r,l)这些边组成的多边形 划分成三角形的方案的集合。
跟上道题的划分是一样的，不过不需要破环成链，因为枚举哪一条边都是一样的。
这里的运算数据太大，需要高精度运算。

//代码一:没有加高精度的代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=110;
int n;
int w[N];
int f[N][N];
int INF=1e18;
void solve()
{cin>>n;for (int i=1;i<=n;i++) cin>>w[i];for (int len=3;len<=n;len++)for (int i=1;i+len-1<=n;i++){int l=i,r=i+len-1;f[l][r]=INF;for (int k=l;k<r;k++){f[l][r]=min(f[l][r],f[l][k]+f[k][r]+w[l]*w[k]*w[r]);}}cout<<f[1][n];
}
signed main()
{ios;int T=1;//cin>>T; while (T--) solve();return 0;
}//代码二:加了高精度的代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=55,M=35,INF=1e9;
int n;
int w[N];
int f[N][N][M];
int c[M];
void add(int a[],int b[])
{memset(c,0,sizeof c);int t=0;for (int i=0;i<M;i++){t +=a[i]+b[i];c[i]=t%10;t /=10;}memcpy(a,c,sizeof c);
}
void mul(int a[],int b)
{memset(c,0,sizeof c);int t=0;for (int i=0;i<M;i++){t +=a[i]*b;c[i]=t%10;t /=10;}memcpy(a,c,sizeof c);
}
int cmp(int a[],int b[])
{for (int i=M-1;i>=0;i--){if (a[i]>b[i]) return 1;else if (a[i]<b[i]) return -1;}return 0;
}
void print(int a[])
{int k=M-1;while (k&&!a[k]) k--;while (k>=0) cout<<a[k--];cout<<endl;
}
int temp[M];
void solve()
{cin>>n;for (int i=1;i<=n;i++) cin>>w[i];for (int len=3;len<=n;len++)for (int i=1;i+len-1<=n;i++){int l=i,r=i+len-1;f[l][r][M-1]=1;for (int k=l+1;k<r;k++){memset(temp,0,sizeof temp);temp[0]=w[l];mul(temp,w[k]);mul(temp,w[r]);add(temp,f[l][k]);add(temp,f[k][r]);if (cmp(f[l][r],temp)>0) memcpy(f[l][r],temp,sizeof temp);}}print(f[1][n]);
}
signed main()
{ios;int T=1;//cin>>T; while (T--) solve();return 0;
}