图形合并类型的区间dp + vector版高精度模板题
高精度模板详见算法基础课
状态表示
f[l][r]
表示多边形的所有边【即:(l,l+1),(1+1,l+2),...,(r-1,r),(l,r)】
划分成三角形的所有方案的最小值
状态计算
根据状态方程的定义,结合图形,枚举区间的分隔点最后得到的就是两个区间:f[l][k]
和f[k][r]
,还有一个三角形,它的顶点分别是w[l]
,w[k]
,w[r]
最终的状态转移方程:f[l][r] = min(f[l][r],f[l][k] + f[k][r] + w[l] * w[k] * w[r])
c++代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 55,INF = 1e9,M = 35;
vector<int> f[N][N]; //每一个数组元素都是vector<int>
//f[l][r]表示多边形的所有边【(l,l+1),(1+1,l+2),...,(r-1,r),(l,r)】划分成三角形的所有方案的最小值
int w[N]; //记录多边形所有的顶点
int n;
vector<int> add(vector<int>& a,vector<int>& b){
int t = 0;
vector<int> c;
for(int i = 0;i < a.size() || i < b.size();++i){
if(i < a.size()) t += a[i];
if(i < b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
if(t) c.push_back(t);
return c;
}
vector<int> mul(vector<int>& a,LL b){
vector<int> c;
LL t = 0;
for(int i = 0;i < a.size() || t;++i){
if(i < a.size()) t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
return c;
}
void reslove(vector<int>& t,int num){ //将num分解后加入到t中
while(num){
t.push_back(num % 10);
num /= 10;
}
if(num) t.push_back(num);
}
bool cmp(vector<int>& a,vector<int>& b)
{
if (a.size() != b.size()) return a.size() > b.size();
int i = (int)a.size() - 1;
while (a[i] == b[i] && i > 0) --i;
return a[i] > b[i];
}
int main(){
cin >> n;
for(int i = 1;i <= n;++i){
cin >> w[i];
}
//区间长度为3(三条边)才能构成一个三角形,
for(int len = 3;len <= n;++len){
for(int l = 1;l + len - 1<= n;++l){
int r = l + len - 1;
//枚举两个区间之间的分割线构成两个区间和一个三角性,范围是[l + 1,r - 1]
//f[l][r] = INF;
for(int i = 0; i < M;++i){ //相当于设置f[l][r]为正无穷
f[l][r].push_back(1);
}
for(int k = l + 1;k <= r - 1;++k){
vector<int> temp;
reslove(temp,w[l]);
mul(temp,w[k]);
mul(temp,w[r]);
add(temp,f[l][k]);
add(temp,f[k][r]);
if(cmp(temp,f[l][r])){ //比较f[l][r]与(f[l][k] + f[k][r] + w[l] * w[k] * w[r])谁比较大
f[l][r] = temp;
}
//f[l][r] = min(f[l][r],f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
}
}
for(int i = n - 1;i >= 0;--i){
cout << f[1][n][i];
}
return 0;
}
大佬,请问这里的M = 35是怎么来的
10^910^910^9*48得来的
大佬,请问这样的状态表示是如何保证一定能够划分出N - 2个三角形的呢?这个题目限制貌似被认为是一定成立的
牛蛙牛蛙