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

傳送門

思路

??根據(jù)題目盐类，很自然的能想到寞奸，先加工 $\color{red}{T}$ 和 $\color{red}{W}$ 的值最大的痕寓。蛋似，并沒有那么好的事情蝇闭，可能 $T$ 大而 $W$ 并沒有那么大。這就要用到貪心的思想了硬毕。我們先使木棍的其中一個(gè)屬性呻引，從大到小進(jìn)行排序，這樣只需要關(guān)心另一個(gè)屬性就可以了吐咳。

??（假設(shè)已經(jīng)按照 $T$ 從大到小進(jìn)行了排列逻悠，對(duì)于有序隊(duì)列中的第一個(gè)木棍，肯定第一個(gè)加工啦韭脊，因?yàn)榧庸り?duì)列就這樣固定了童谒，別問我為什么，因?yàn)橐呀?jīng)按照 $T$ 排好序了沪羔，這樣加工必然滿足 $T$ 大于后面的木棍的 $T$ 值）

??接下來就從第一根木棍看起饥伊，只要它之后的其他木棍的 $W$ 值小于它，就不會(huì)產(chǎn)生準(zhǔn)備時(shí)間（此處滿足了 $T$ 大于蔫饰，因?yàn)殛?duì)列有序琅豆，就是按照 $T$ 從大到小排列的，后面的必然小于前面的篓吁。 $W$ 值大于就是限定條件）不一定是連續(xù)的哦茫因，但只要保證木棍在它之后就可以呦。然后杖剪，神奇的事情出現(xiàn)了冻押，你有沒有發(fā)現(xiàn)這是在求最長下降子序列（神馬，你不知道怎么求盛嘿，那去看我這篇先LIS&LDS)洛巢。

??最后求準(zhǔn)備時(shí)間總共多少的問題，就變成了求每個(gè)盡可能長的下降子序列的個(gè)數(shù)啦孩擂。如何求這個(gè)個(gè)數(shù)呢狼渊，只需要求隊(duì)列中關(guān)于 $W$ 的最長上升子序列，看這個(gè)子序列里包含多少個(gè)元素就行了??类垦。

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);//按照其中的一個(gè)屬性排序 
    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數(shù)組中狈邑，第一個(gè)大于當(dāng)前值的下標(biāo)
            k = lower_bound(dp, dp+count, value)-dp; 
            dp[k] = wood[i].W;
        }
    }
    cout << count << endl; 
    return 0;
}

最后編輯于：2019.07.24 11:41:59

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者