题目描述
一根木棍有二维属性l,w,每加工一根木棍会消耗一分钟,但当上一次加工的木棍二维属性都大于等于当前是不消耗时间
样例
input
5
4 9 5 2 2 1 3 5 1 4
output
2
算法
dp
-
dilworth定理
在有穷偏序集中,任何反链最大元素数目等于任何将集合到链的划分中链的最小数目
即不下降子序列最小个数等于最大上升(严格)子序列的长度 -
首先,考虑一维l,若果第i根不消耗时间则它加工一定在某一根l比它长的木棍后面,可以根据l进行从大到小排序
- 然后对w求最长严格上升子序列的长度,即为最少可划分出的不下降子序列的数量
- 为了使w的最长严格上升子序列的长度尽可能短,要以l为第一根据,w为第二根据,从大到小排序
C++ 代码
void solve()
{
int n;
std::cin >> n;
for(int i=1;i<=n;i++) std::cin >> p[i].first >> p[i].second;
std::sort(p+1,p+n+1,[](PII x, PII y){return x.first==y.first?x.second>y.second:x.first>y.first;});
int len = 0; maxv[0] = -INF;
for(int i=1;i<=n;i++)
{
int t = std::lower_bound(maxv,maxv+len+1,p[i].second)-maxv;
maxv[t] = p[i].second;
len = std::max(len,t);
}
std::cout << len << "\n";
}