知识点：DP

Updated on 10.4：感谢 @七色丶人偶使 指出错误！

原题面： Luogu

---

扯

考试题，场上写挂爆零了没到 300= =
写错变量名就是真的离谱。

---

题意简述

给定两数列 \(a,b\)，长度分别为 \(n,m\)，可以做如下操作：
删除 \(a\) 的最后 \(x(x\ge 1)\) 个数，设其和为 \(sum_a\)，删除 \(b\) 的最后 \(y(y\ge 1)\) 个数，其花费为 \(sum_b\)。
该次操作的总花费为 \((sum_a - x) \times (sum_b - y)\)。
一直操作到 \(a,b\) 均为空，最小化所有操作的总花费。
\(1\le n,m\le 2000\)，\(1\le a_i\le 1000\)。

---

分析题意

40pts

感谢出题人送的超高暴力分！

暴力 DP，设 \(f_{i,j}\) 表示将数列 \(a\) 删剩下 \(i\) 个，数列 \(b\) 删剩下 \(j\) 个时，需要的最小的花费。
转移时枚举两数列最后一次删除的长度 \(x,y\)，则有很简单但是写起来很长的方程：

\[f_{i,j} = \left\{ \min_{x=1}^{n-i}\min_{y=1}^{m-j} \left(f_{i+x,j+y} + \left(\sum_{k=i+1}^{i+x}a_k - x\right) \times \left(\sum_{k=j+1}^{j+y}b_l - y\right)\right)\right\} \]

可以使用前缀和预处理 \(\sum a\) 和 \(\sum b\)，转移复杂度 \(O(n^2m^2)\)。
由于要保证不出现一个数列为空，一个不为空的情况，统计答案时枚举最后一次删除的长度，则有：

\[ans = \min_{i=1}^{n}\min_{j=1}^{m}\left\{ f_{i,j} + \left(\sum_{k=1}^{i} a_k - i\right) \times \left(\sum_{l=1}^{j} b_l - j\right)\right\} \]

统计答案复杂度为 \(O(nm)\)，总复杂度为 \(O(n^2m^2)\)。

---

一点性质

发现选择一个数的贡献，是该数的值，减去 1。
考虑将所有数都减去 1，转移方程变为：

\[f_{i,j} = \left\{ \min_{x=1}^{n-i}\min_{y=1}^{m-j} \left(f_{i+x,j+y} + \sum_{k=i+1}^{i+x}a_k \sum_{k=j+1}^{j+y}b_l \right)\right\} \]

转移方程会比较好写，并且减小了某些分析的难度。
以下分析均在此方程下展开。

---

60pts

一个结论：每次各删除 \(a\)，\(b\) 中的一段数时，一定有一边删除的个数为 \(1\)。

是不是很扯皮？
略证，对于某次操作，设删除的部分为 \(a_i \sim a_{i+x}\)，\(b_j \sim b_{j+y}\)。删除它们的花费即为：

\[\sum_{k=i}^{i+x} a_k\sum_{l=j}^{j+y} b_l \]

设存在一组 \(x',y'\)，满足：\(1\le x'，\(1\le y'。
如果先删除 \(a_{i+x'}\sim a_{i+x}\) 和 \(b_{j+y'} \sim b_{j+y}\)，再删除 \(a_{i}\sim a_{i+x'-1}\) 和 \(b_{j}\sim b_{j + y' - 1}\)，其花费为：

\[\begin{aligned} &\sum_{k=i}^{i+x'-1} a_k\sum_{l=j}^{j+y'-1} b_l + \sum_{k=i+x'}^{i+x} a_k\sum_{l=j+y'}^{j+y} b_l\\ \le& \sum_{k=i}^{i+x} a_k\sum_{l=j}^{j+y} b_l\\ =& \left(\sum_{k=i}^{i+x'-1} a_k + \sum_{l=j}^{j+y'-1} b_l\right) \times \left(\sum_{k=i+x'}^{i+x} a_k + \sum_{l=j+y'}^{j+y} b_l\right) \end{aligned}\]

将一大段被删除的数划分成更小的段，代价一定不会更劣。
则最后一定会划分出长度为 \(1\) 的删除段，结论成立。

---

则可修改状态转移方程，钦定一边选仅一个，仅需枚举另一边的选择个数，即仅枚举 \(x\) 或 \(y\)。
转移复杂度变为 \(O(nm(n + m))\)。

---

100pts

考虑优化状态。
发现转移时需要钦定一边只选择 \(1\) 个。若钦定 \(a\) 仅选择 \(1\) 个，有用状态的 \(i'\) 均为当前状态的 \(i+1\)。

设 \(f_{i,j}\) 表示将数列 \(a\) 删剩下 \(i\) 个，数列 \(b\) 删剩下 \(j\) 个时，且上一次删数时钦定 \(a\) 删除了 \(1\) 个，需要的最小花费。
同理，设 \(g_{i,j}\) 表示上一次删数时钦定 \(b\) 删除了 \(1\) 个，需要的最小的花费。

---

考虑转移，以 \(f_{i,j}\) 为例，分类讨论：

1. \(a,b\) 均删除 \(1\) 个，代价即为 \(a_{i+1}\times b_{j+1}\)。
   上一次删多少不受影响，显然可以从 \(f_{i+1,j+1}\) 和 \(g_{i+1,j+1}\) 转移而来。
   则有转移：

   \[f_{i,j} = \min\left\{ f_{i+1,j+1},g_{i+1,j+1}\right\} + a_{i+1}\times b_{j+1} \]

2. \(a\) 删除 \(1\) 个，\(b\) 删除 \(y(y>1)\) 个，则其代价为 \(a_{i+1}\times \sum_{k=j+1}^{j+y} b_{k}\)。
   发现代价可以拆成 \(a_{i+1}\times b_{j+1} + a_{i+1} \times \sum_{k=j+2}^{j+y} b_k\)。
   对于后一项，其已经被统计到 \(i'=i,j'=j+1\) 的情况中了。
   则有转移：

   \[f_{i,j} = f_{i,j+1} + a_{i+1}\times b_{j+1} \]

综上，则有：

\[f_{i,j} = \min\left\{ f_{i,j+1},f_{i+1,j+1},g_{i+1,j+1}\right\} + a_{i+1}\times b_{j+1} \]

同理，对于 \(g_{i,j}\)，有：

\[g_{i,j} = \min\left\{ g_{i+1,j},f_{i+1,j+1},g_{i+1,j+1}\right\} + a_{i+1}\times b_{j+1} \]

每次转移是 \(O(1)\) 的，转移总复杂度 \(O(nm)\)。
答案即为 \(\min \{f_{0,0}, g_{0,0}\}\)

---

为啥你的状态和别人不一样啊？

发现上面两个转移方程形式基本相同，所以可以合并状态。
就得到了其他题解的形式。

---

爆零小技巧

有些看起来无意义的状态仍然对答案有贡献。
比如当 \(i,j\) 其中有一个为 \(0\) 时，

---

代码实现

//知识点：DP 
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define ll long long
#define min std::min
const int kMaxn = 2e3 + 10;
//===========================================================
int n, m, a[kMaxn], b[kMaxn];
ll f[kMaxn][kMaxn], g[kMaxn][kMaxn];
//===========================================================
inline int read() {
  int w = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmin(ll &fir, ll sec) {
  if (sec < fir) fir = sec; 
}
//===========================================================
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; ++ i) a[i] = read() - 1;
  for (int i = 1; i <= m; ++ i) b[i] = read() - 1;
  
  memset(f, 127, sizeof (f));
  memset(g, 127, sizeof (g));
  f[n][m] = g[n][m] = 0;
  
  for (int i = n - 1; i >= 0; -- i) {
    for (int j = m - 1; j >= 0; -- j) {
      ll val = 1ll * a[i + 1] * b[j + 1];
      Chkmin(f[i][j], min(f[i][j + 1], min(f[i + 1][j + 1], g[i + 1][j + 1])) + val);
      Chkmin(g[i][j], min(g[i + 1][j], min(f[i + 1][j + 1], g[i + 1][j + 1])) + val);
    }
  }
  printf("%lld\n", min(f[0][0], g[0][0]));
  return 0;
}
/*
3 2
1 2 3 
1 2 
*/