挑战练习题2.3动态规划 poj1065 Wooden Sticks 最长递减子序列

题目链接:

题意:

C小加有一些木棒，它们的长度和质量都已经知道，需要一个机器处理这些木棒，机器开启的时候需要耗费一个单位的时间，如果第i+1个木棒的重量和长度都大于等于第i个处理的木棒，那么将不会耗费时间，否则需要消耗一个单位的时间。因为急着去约会，C小加想在最短的时间内把木棒处理完，你能告诉他应该怎样做吗？

题解:

最小值其实等于按l递增排序后stick按w最长下降子序列的长度L

就是求最长递减子序列。。
dp[i] := 长度为i+1的下降子序列中末尾元素的最大值

代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 #define MS(a) memset(a,0,sizeof(a))
 8 #define MP make_pair
 9 #define PB push_back
10 const int INF = 0x3f3f3f3f;
11 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
12 inline ll read(){
13     ll x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 //////////////////////////////////////////////////////////////////////////
19 const int maxn = 1e5+10;
20 
21 pair<int,int> sticks[maxn];
22 int ans[maxn];
23 
24 int main(){
25     int T = read();
26     while(T--){
27         int n = read();
28         for(int i=0; i<n; i++){
29             cin >> sticks[i].first >> sticks[i].second;
30         }
31         sort(sticks,sticks+n);
32 
33         memset(ans,-1,sizeof(ans));
34 
35         int mx = 0;
36         for(int i=0; i<n; i++){
37             // int L=0,R=5001,p=1;
38             // while(L<=R){
39             //  int mid = (L+R)/2;
40             //  if(ans[mid] > sticks[i].second) p=mid+1,L=mid+1;
41             //  else R=mid-1;
42             // }
43             int p = lower_bound(ans+1,ans+1+n,sticks[i].second,greater<int>())-ans;
44             ans[p] = sticks[i].second;
45             mx = max(mx,p);
46         }
47 
48         cout << mx << endl;
49     }
50 
51     return 0;
52 }