Description
Solution
每次选择花费最大的地方切,然后按照题意(O(n))模拟即可。
证明如下:
(1.)若两次切割都是横向或竖向,且花费小的比花费大的先切割。
设花费小的切割的时候需要切割(a)次,花费大的切割的时候需要切割(b)次,因为中间可能切割了任意次另外一个方向,所以(a 。
那么将它们交换,则花费大的对答案的贡献一定小于等于原先的贡献,所以同一方向将花费大的放在花费小的前面一定最优。
(2.)若两次切割不是同一方向,且话费晓得比花费大的先切割。
设切割前若切花费小的方向花费小的方向需要切(a)刀,切花费大的方向需要切(b)刀。
那么先切花费小的,花费大的就需要切(b + 1)刀,反之亦然。
因为花费大的(\times (b + 1) +)花费小的(\times a >=)花费大的(\times b +)花费小的(\times (a + 1)),所以先切花费大的一定最优。
所以最后复杂度就是排序的复杂度。[Q.E.D. ]
Code
#include #include #include #include using namespace std; #define ll long long const int N = 20000; int n, m, num, sum[2]; struct Node { int cost, type; } cut[N + 50]; void Read(int &x) { x = 0; int p = 0; char st = getchar(); while (st '9') p = (st == '-'), st = getchar(); while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar(); x = p ? -x : x; return; } bool Cmp(Node a, Node b) { return a.cost > b.cost; } int main() { ll ans = 0; Read(n); Read(m); for (int i = 1, x; i <= n - 1; i++) Read(x), cut[++num] = (Node){x, 1}; for (int i = 1, x; i <= m - 1; i++) Read(x), cut[++num] = (Node){x, 0}; sort(cut + 1, cut + num + 1, Cmp); for (int i = 1; i <= num; i++) { ans = ans + 1LL * (sum[cut[i].type ^ 1] + 1) * cut[i].cost; sum[cut[i].type]++; } printf("%lld", ans); return 0; }