因为要切成 \(1\times 1\) 的小方块，所以这 \((n-1)+(m-1)\) 条线的每条线都会挨一刀，只需要将顺序确定下来，就有可能计算出总代价。
贪心地考虑，对于同一侧来说，代价大的切割要尽早处理，否则一旦在另一个方向上进行了一次切割，这一刀的代价就会增加一倍，代价小的加倍总比代价大的加倍要优，所以我们可以直接把横、竖线切割的代价分别从大到小排序；而对于一横一竖两刀来说，同理应该先切代价大的。于是想到可以用两个指针按照上述方案同步扫描排序后的两个数组，统计答案。
因为“不能把两块木板拼起来切割”，所以每横着切一刀的费用 \(a_i\) 要乘一个系数，即 \(竖着切的刀数+1\)；每竖着切一刀的费用 \(b_i\) 也要乘一个系数，即 \(横着切的刀数+1\)。不妨开两个变量，在指针扫描的同时统计两个方向各切了多少刀，即可统计出答案。
下面是 AC 代码：
#include <bits/stdc++.h>
using i64 = long long;
bool compare(int x, int y)
{
return x > y;
}
int main()
{
int n, m;
std::cin >> n >> m;
std::vector<i64> rowCutCosts(n - 1);
std::vector<i64> columnCutCosts(m - 1);
for (int i = 0; i < n - 1; i++)
{
std::cin >> rowCutCosts[i];
}
for (int i = 0; i < m - 1; i++)
{
std::cin >> columnCutCosts[i];
}
std::sort(rowCutCosts.begin(), rowCutCosts.end(), compare);
std::sort(columnCutCosts.begin(), columnCutCosts.end(), compare);
i64 sumCost = 0;
int i = 0, j = 0;
while (i < n - 1 && j < m - 1)
{
if (rowCutCosts[i] >= columnCutCosts[j])
{
sumCost += (i64)rowCutCosts[i++] * (j + 1);
}
else
{
sumCost += (i64)columnCutCosts[j++] * (i + 1);
}
}
for (; i < n - 1; i++)
{
sumCost += (i64)rowCutCosts[i] * (j + 1);
}
for (; j < m - 1; j++)
{
sumCost += (i64)columnCutCosts[j] * (i + 1);
}
std::cout << sumCost << '\n';
return 0;
}
注意输入数据是 \(n-1,m-1\) 个数！