定义 $C=A\times B$ 满足 $C_i=\max_{j\lor k=i}(A_j+B_k)$。
约定 $\operatorname{concat}(A,B)$ 表示把 A，B 数组接起来，$\max(A,B)$ 表示 A，B 按位取 max。
考虑用类似 karatsuba 的搞法。
假设 A，B 长度都是 $2^n$，需要计算 $C=A\times B$，考虑按照下标的二进制最高位把 A,B,C 分成前后两半，即：
\[\begin{aligned} A=\operatorname{concat}(A_0,A_1)\cr B=\operatorname{concat}(B_0,B_1)\cr C=\operatorname{concat}(C_0,C_1)\cr \end{aligned}\]则有：
\[\begin{aligned} C_0&=A_0\times B_0\cr C_1&=\max(A_1\times B_0,A_0\times B_1,A_1\times B_1)\cr &=\max (A_1\times B_0,\max(A_0,A_1)\times B_1) \end{aligned}\]于是递归处理 3 个长度为 $2^{n-1}$ 的子问题即可。复杂度 $T(n)=3T(n-1)+O(2^n)=O(3^n)$。
#define upd(i, j) c[i | j] = max(c[i | j], a[i] + b[j])
inline void solve(ll *a, ll *b, ll *c, ll *tmp, ll len) {
if (len <= 4) {
upd(0,0);upd(0,1);upd(0,2);upd(0,3);
upd(1,0);upd(1,1);upd(1,2);upd(1,3);
upd(2,0);upd(2,1);upd(2,2);upd(2,3);
upd(3,0);upd(3,1);upd(3,2);upd(3,3);
return;
}
ll hlen = len >> 1;
solve(a, b, c, tmp, hlen);
solve(a + hlen, b, c + hlen, tmp, hlen);
for (ll i = hlen; i < len; i++) {
tmp[i - hlen] = a[i];
a[i] = max(a[i], a[i - hlen]);
}
solve(a + hlen, b + hlen, c + hlen, tmp + hlen, hlen);
memcpy(a + hlen, tmp, sizeof(ll) * hlen);
}
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: