[贪心]木棍加工—洛谷P1233

传送门

木棍加工P1233

思路

  根据题目，很自然的能想到，先加工 和的值最大的。蛋似，并没有那么好的事情，可能大而并没有那么大。这就要用到贪心的思想了。我们先使木棍的其中一个属性，从大到小进行排序，这样只需要关心另一个属性就可以了。

  （假设已经按照从大到小进行了排列，对于有序队列中的第一个木棍，肯定第一个加工啦，因为加工队列就这样固定了，别问我为什么，因为已经按照排好序了，这样加工必然满足大于后面的木棍的值）

  接下来就从第一根木棍看起，只要它之后的其他木棍的值小于它，就不会产生准备时间（此处满足了大于，因为队列有序，就是按照从大到小排列的，后面的必然小于前面的。值大于就是限定条件）不一定是连续的哦，但只要保证木棍在它之后就可以呦。然后，神奇的事情出现了，你有没有发现这是在求最长下降子序列（神马，你不知道怎么求，那去看我这篇先LIS&LDS)。

  最后求准备时间总共多少的问题，就变成了求每个尽可能长的下降子序列的个数啦。如何求这个个数呢，只需要求队列中关于的最长上升子序列，看这个子序列里包含多少个元素就行了🤪。

AC代码

#include<iostream>
using namespace std;
#include<algorithm>
int dp[5010];

typedef struct wood{
    int L;
    int W; 
}Wood;
Wood wood[5010];

int cmp(Wood w1, Wood w2){
    return w1.L > w2.L;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> wood[i].L >> wood[i].W;
    } 
    sort(wood, wood+n, cmp);//按照其中的一个属性排序 
    int count = 1;
    dp[count] = wood[0].W;
    int k;
    //求最长上升子序列 
    for(int i = 1; i < n; i++){
        if(dp[count] < wood[i].W){
            dp[++count] = wood[i].W;        
        }
        else{
            int value = wood[i].W;
            //找出在dp数组中，第一个大于当前值的下标
            k = lower_bound(dp, dp+count, value)-dp; 
            dp[k] = wood[i].W;
        }
    }
    cout << count << endl; 
    return 0;
}