洛谷 P1233 木棍加工（贪心，递增子串DP）

题目大意：

有矩形A1，A2... ... An. 每个矩形有长宽w,h。现在已知cost：

（1）若矩形a的w,h小于矩形b的w，h，那么没有cost

（2）其它情况cost+1.

现在已知矩形A1，A2... ，问怎么得到最少cost.

解题思路：

首先，我们要用贪心。这里有一个最优边界，若矩形a1,a2,a3互不包含（即cost肯定有3，之间长宽没有包含关系）.

所以，最优边界就是最大互不包含的矩形数！这个是本题的关键结论，要证明，我们可以用反证法。

若我们找到5个这种不包含的矩形，其它的所有的矩形肯定在这些矩形的内部，若有矩形不包含于这5个矩形，那么和最多不相交矩形数矛盾，所以我们可以证明最少cost等于 最多互不包含的矩形数。

然后我们要找到互不包含的矩形数，这里我们首先对w从大到小排列，然后h找最长的单调递增序列。

序列长度即为cost，我们可以证明这个就是互不包含的矩形数。

废话：这题贪心告诉我们，一定要想办法证明最优边界，提出自己的猜想。

另外，先排序再找最长单调递增子串这种tricky的做法也可以学习。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
bool cmp(pair<int, int> fir, pair<int, int> las) {
  if (fir.first <= las.first && fir.second <= las.second)return false;
  else return true;
}
int main() {

  int n; cin >> n;
  vector<pair<int, int>> arrmv;
  for (int i = 0; i< n; i++) {
    int a, b; cin >> a >> b;
    arrmv.push_back(make_pair(a, b));
  }
  vector<int> L(MAXN);
  int P[MAXN];
  int P_id[MAXN];
  int lis = 0;
  int lis_end;
  sort(arrmv.begin(), arrmv.end(), greater<pair<int, int>>());
  vector<int> L2;
  for (int i = 0; i < n; i++) {
    L2.push_back(arrmv[i].second);
  }
  for (int i = 0; i<n; i++) {
    int pos = lower_bound(L.begin(), next(L.begin(), lis), L2[i]) - L.begin();  //maybe cmp ...
    L[pos] = L2[i];
    P_id[pos] = i;
    P[i] = pos == 0 ? -1 : P_id[pos - 1];
    if (pos == lis) {
      lis_end = i;
      lis = pos + 1;
    }
  }

  int count = 0;
  for (int poi = lis_end; poi != -1; poi = P[poi]) {
    count++;
  }
  cout << count << endl;
  return 0;
}