时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

In the wood industry, it is very common to make big wood boards by combining planks. To combine several planks into boards, the carpenter may cut some of the planks horizontally and discard one of the two parts, such that the heights of all planks are equal. Then, the planks are joined together, forming a big wood board. The height of the board is the common height of the planks, and the width of the board is the sum of the widths of the planks.

img

However, cutting planks may result in huge wastes. The problem is, given n planks, determine the minimum total wasted area of planks to make k boards from these planks. You may freely reorder and combine these planks. Note that the mechanical properties of a plank are anisotropic, so you can’t rotate the planks. Also, all planks must be used; you cannot discard any whole plank.

输入描述:

The first line of the input contains two integers $n$, $k$
($1 \leq n \leq 5000, 1 \leq k \leq 2000, k \leq n$), denoting the number of planks given and the number of boards to make.Each of the remaining n lines contains two integers w, h ($1 \leq w, h \leq 10^7$), denote the width and the height of a given plank.

输出描述:

Output the minimum wasted area as an integer.

示例1

输入

1
2
3
4
3 2
3 3
4 7
2 5

输出

1
4

示例2

输入

1
2
3
4
5
6
7
6 3
1 1
1 2
1 3
1 4
1 5
1 6

输出

1
3

题意

给你 $n$ 块木板，其摆放方式不能动，即竖着的是高，横着的是宽，现在让你去切割一些木板，合并一些木板，使得最后剩下的木板总数为 $k$ ，问最小浪费的面积是多少。注意，切割木板只能横着切，即若把宽对着 $x$ 轴，高对着 $y$ 轴，只能平行于 $x$ 轴去切割木板，木板被切成两部分后，上半部分即丢弃了（也就是浪费的面积），下半部分可以与和它同高的木板合并成一块。

解决方案

预处理

  • 首先是一个预处理，对这些木板按照高度去排序，高相同的则把宽较小的放前面，为什么呢？很容易想到，我们如果要把一块木板和别的木板合并，那么肯定是和高度小于等于它的合并，而且必然是优先合并高度与它相近的（这样浪费少），可能有人会问，为什么不能和高度比它高的木板合并呢？仔细想想，其实这是同一种情况，只不过“主角”不一样，对于与他合并的更高那块木板来说，不就是向下合并了吗？

  • 排好序之后，其实就能够看出这个题目是个dp题了，考虑前 $j$ 块木板合并为 $i$ 块木板的情况的浪费面积为 $dp[i][j]$， 这样状态就已经定义好了，那么状态转移方程也容易想出来（这个容易想出来是你有一定的dp基础，刷过至少几十道dp题的意思），当我们求 $dp[i][j]$ 时，只需要考虑第 $j$ 块木板向前合并多少块，然后前面剩下的木板合并为 $i - 1$ 块，则转移方程为：

  • 其中 $cost{k + 1\rightarrow j}$ 表示从第 $k + 1$ 块至第 $j$ 块合并为一块的浪费面积，这个可以基于一定的预处理得到，以下给出公式：
  • 其中 $suma[j]$ 表 $1$ ~ $j$ 木板的面积之和， $sumw[j]$ 表 $1$ ~ $j$ 的木板宽度之和，$h(k + 1)$ 表第 $k + 1$ 块木板的高。

优化

这样我们得到了一个相当复杂的状态转移方程。

好了，重点来了，如果我们直接就这么写，是 $O(kn^2)$ 的复杂度，emmmmmmmm,看到这个数据量，无疑是会TLE的，那么接下来就是本文的焦点，斜率优化。

这题的重点就是如果能够在 $O(1)$ 的时间内把那个 $min$ 求出来，博主这种菜鸡只能想到线段树或者单调队列优化了，但是想了半天都感觉这两种数据结构在这题里是没有用武之地的，然后从网上学了一波斜率优化，斜率优化的使用条件比较苛刻，但很多时候很多dp似乎都是满足它的使用条件的（黑人问号❓）。

我们假设现在有两个$k_1,k_2$值用于更新 $dp[i][j]$ ，假设 $k_2$ 优于 $k_1$，即

对这个式子进行整理（不用怀疑，因为斜率优化的重点在于推出斜率表达式，得到：

其中(假设当前在求 $dp[i][j]$ ,用 $dp[i-1][k]$ 更新 $dp[i][j]$ )：

显然，$f(k)$ 的值与 $j$ 的取值无关，不等式右边的 $sumw[j]$ 对于当前求的 $dp[i][j]$ 来说是个定值，而且 $sumw[j]$ 随着 $j$ 增大时递增的（后面会讲，这是一个重要条件），设①式为 $g[k_2, k_1]$ ，则只需 $g[k_2, k_1]\leq sumw[j]$ 则有 $k_2$ 优于 $k_1$。

由于我们的内层循环（即 $j$ )是按照顺序（$1\rightarrow n$）进行dp的，不妨设 $k1 < k2 < j$ （对，你没看错，即使我们现在求的就是 $dp[i][j]$ 的值，但这里考虑了 $j$, 因为这里是 $j$ 应该如何入队，与 $dp[i][j]$ 的值无关），若 $g[j,k_2]\leq g[k_2,k1]$ ，则 $k_2$ 一定不是最优解，证：

若 $g[j,k_2] \leq sumw[j]$ 则 $j$ 比 $k_2$ 优。

若 $g[j,k_2]\geq sumw[j]$ 则 $k_2$ 比 $j$ 优，但 又 $g[k_2,k_1]\geq g[j,k_2]$，所以 $g[k_2,k_1] \geq sumw[j]$ ，所以 $k_1$ 优于 $k_2$ 。

所以我们需要维护一个队列，队列内的元素 满足相邻元素间 ，那么到求 $dp[i][j]$ 时，只需判断队首的两个元素 的斜率 与 的关系。

若 $g[a_2, a_1]\leq sumw[j]$ ，则 $a_2$ 必比 $a_1$ 优，所以可以把队首元素 $a_1$ 弹出，直到队内元素数量 = 1 或者 $g[a_2, a_1] \geq sumw[j]$ ，此时 $a1$ 比 $a_2$ 优，则 $a_1$ 就是最优解，为什么？我们前面说了，这个队列的元素间满足的关系！所以有 $a_1$ 优于 $a_2$ ，$a_2$ 优于 $a_3$ ，依次类推，所以 $a_1$ 即队首元素为最优！这就是斜率优化的精髓！

更新完 $dp[i][j]$ 之后，相应的，$j$ 也需要入队，为了保持队列元素间斜率的递增性质，依据上面已经证明过的弹出性质，设队列的大小为 $m$, 则当 时，弹出 即队尾元素，直到队列元素数量 = 2 或

那又为什么断定队首被出队的元素以后就没用了呢？就因为 $sumw$ 是递增的！这就是斜率优化的使用条件。

代码

这题有个坑爹的地方，就是有些地方的乘法可能会爆long long， 所以要用__int128_t，博主由于这个原因WA了很多发……，找了很久才找出来。

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
#define zpw                    \
  ios::sync_with_stdio(false); \
  cin.tie(NULL);               \
  cout.tie(NULL)

using namespace std;

typedef long long ll;
typedef __int128_t llint;

const int maxn = 5e3 + 10;

struct node {
  ll w, h;

  bool operator<(const node &t) const {
    if (h == t.h) {
      return w < t.w;
    } else {
      return h < t.h;
    }
  }
} p[maxn];

ll dp[2010][maxn];
ll sumw[maxn];
ll suma[maxn];

ll getUp(int i, int k1, int k2) {
  ll t1 = dp[i][k1] - suma[k1] + p[k1 + 1].h * sumw[k1];
  ll t2 = dp[i][k2] - suma[k2] + p[k2 + 1].h * sumw[k2];
  return t1 - t2;
}

ll getDown(int k1, int k2) { return p[k1 + 1].h - p[k2 + 1].h; }

ll getDp(int i, int j, int k) {
  return dp[i - 1][k] + suma[j] - suma[k] - p[k + 1].h * (sumw[j] - sumw[k]);
}

int main() {
  zpw;
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].w >> p[i].h;
  }
  sort(p + 1, p + n + 1);
  for (int i = 1; i <= n; i++) {
    sumw[i] = sumw[i - 1] + p[i].w;
    suma[i] = suma[i - 1] + p[i].w * p[i].h;
    dp[1][i] = suma[i] - sumw[i] * p[1].h;
  }

  for (int i = 2; i <= k; i++) {
    deque<int> q;
    q.push_back(0);
    for (int j = 1; j <= n; j++) {
      while (q.size() >= 2) {
        if ((llint)getUp(i - 1, q[1], q[0]) <=
            (llint)sumw[j] * (llint)getDown(q[1], q[0])) {
          q.pop_front();
        } else {
          break;
        }
      }
      dp[i][j] = getDp(i, j, q.front());
      while (q.size() >= 2) {
        int m = q.size();
        llint t1 = (llint)getUp(i - 1, j, q[m - 1]) *
                   (llint)getDown(q[m - 1], q[m - 2]);
        llint t2 = (llint)getUp(i - 1, q[m - 1], q[m - 2]) *
                   (llint)getDown(j, q[m - 1]);
        if (t1 <= t2) {
          q.pop_back();
        } else {
          break;
        }
      }
      q.push_back(j);
    }
  }
  cout << dp[k][n] << endl;
  return 0;
}