概览
其实就是矩阵乘法的变形
很神奇的是,矩阵乘法原来其实也可以从图形结合的角度看待,即图形的边与定点。
合并两个相关的点,其实就直接关联了三个边。
最后合成的矩阵的大小不一样??
同凸多边形划分,矩阵相乘
题解
(2,3) (3,5) (5,10) (10,2)
换种表达方式
2 3 5 10 2
所以实际还要往后面乘一个数,这样缺点?
这样表达方式也要学习。一开始自己的想法居然是利用pair, 然后预处理,看来还是要多观察数据的特性
f[l,r] 所有将[l,r]合并的方式的Max
这种划分方式,中间是公用的!
f[l,r] = max(f[l,r], f[l,k]+f[k,r]+w[l]w[k]w[r])
特殊情况解释:
1. 如何只有一个矩阵,代价为0,len从3开始枚举没问题
2. 最后一次合并相当于[l,k],[k,r]
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n;
int w[N], f[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> w[i];
w[i + n] = w[i];
}
memset(f, 0, sizeof f);
for (int len = 3; len <= n + 1; len ++)
for (int l = 1; l + len - 1 <= n * 2; l ++) {
int r = l + len - 1;
for (int k = l + 1; k < r; k ++) // 最长的串,只计算一边的内容,所以l+1
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[r] * w[k]);
}
int res = 0;
for (int i = 1; i <= n; i ++) res = max(res, f[i][i + n]); // 注意这里实际上默认的是长度公式为n+1
cout << res << endl;
return 0;
}
想问一下为什么是len <= n + 1而不是len <= n呢?
len<=n也能过
因为是环形的呀
唔 再补充一下 如果是
2 3 5 10
这四个数 而你选择的合并的区间为(2 3) (3 5) (5 10) (10 2)
则说明实际上用到的应该是2 3 5 10 2
五个数 所以需要开到 n + 1 的长度(根据实际意义出发)
当然如果你采用
环形石子合并
那道题的思路的话len
可以枚举从1~n
但随之而变的还有状态转移方程,k就不再是共用的了~