問題闡述

??給定若干個(gè)工作的開始時(shí)間、結(jié)束時(shí)間和權(quán)重（可以理解成重要程度），求出能完成的最大的工作權(quán)重（盡可能地完成更重要的工作），當(dāng)然必須滿足各個(gè)工作相容。如以下三個(gè)工作：
????????????? 開始時(shí)間 ???結(jié)束時(shí)間 ???權(quán)重
工作1???????????0???????????????3??????????????4
工作2???????????5???????????????6??????????????5
工作3???????????2???????????????8?????????????10
??由不帶權(quán)重的區(qū)間調(diào)度方法，依次結(jié)束時(shí)間最早且相容的工作，這里就選出{1, 2}，能實(shí)現(xiàn)的最大權(quán)重是4+5=9。而顯而易見，選擇{3}權(quán)重可達(dá)到10，因此最早結(jié)束時(shí)間的貪心策略在帶權(quán)重的區(qū)間調(diào)度問題里已不適用。

分析

各工作開始與結(jié)束時(shí)間

??給出上圖所示8個(gè)工作的開始結(jié)束時(shí)間，按結(jié)束時(shí)間升序排序（區(qū)間調(diào)度問題一般都會(huì)先按結(jié)束時(shí)間升序排序）。 數(shù)據(jù)說明如下：

• 工作數(shù)目n
• 聲明結(jié)構(gòu)體數(shù)組存儲(chǔ)工作的開始、結(jié)束時(shí)間和權(quán)值

struct JOB{
    int s, e, v;
    JOB(int s=0, int e=0, int v=0):s(s), e(e), v(v){}
}job[maxn];

• dp[n]，dp[i]表示對(duì)前1個(gè)工作考慮結(jié)束后所能達(dá)到的最大權(quán)值
• frt[n]，frt[i]表示序列中前一與之相容的最大工作編號(hào)。如frt[8]=5，frt[6]=2

按結(jié)束時(shí)間排序

??考慮狀態(tài)轉(zhuǎn)移方程。對(duì)于每個(gè)工作i，比較dp[i-1]和v[i]+dp[frt[i]]，取較大者為dp[i]

狀態(tài)轉(zhuǎn)移方程

代碼實(shí)現(xiàn)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int maxn = 205;
struct JOB{
    int s, e, v, index;
    JOB(int s=0, int e=0, int v=0, int index=0):s(s), e(e), v(v), index(index){}
}job[maxn];
int frt[maxn], dp[maxn];

bool cmpe(JOB a, JOB b){ //定義按結(jié)束時(shí)間升序排序的排序規(guī)則
    return a.e<b.e;
}
/*bool cmps(JOB a, JOB b){ //定義按開始時(shí)間升序排序的排序規(guī)則
    return a.s<b.s;
}*/

int main()
{
    int n; cin >> n;
    //JOB a=(1,2,3);
    memset(frt, 0, sizeof(frt));
    memset(dp, 0, sizeof(dp));
    for(int i=1;i<=n;i++) cin >> job[i].s >> job[i].e >> job[i].v;
    //按結(jié)束時(shí)間升序排序，并為元素編號(hào)
    sort(job, job+n, cmpe);
    for(int i=1; i<=n; i++) job[i].index=i;
    //求frt[]數(shù)組
    //sort(job, job+n, cmps); //按開始時(shí)間升序排列
    for(int i=n;i>0;i--){
        for(int j=n-1;j>0;j--){
            if(job[j].e<=job[i].s) {frt[i]=job[j].index; break;}
        }
    }
    //sort(job, job+n, cmpe);
    for(int i=1;i<=n;i++){
        dp[i] = max(dp[i-1], dp[frt[i]]+job[i].v);
    }
    cout << dp[n];
    return 0;
}

老師的ppt里有一句話，“按開始時(shí)間排序后，計(jì)算frt數(shù)組的復(fù)雜度為O(n)”，但我沒想出來怎么個(gè)O(n)法，上面代碼還是用的簡(jiǎn)單的遍歷，希望看到這里的朋友能不吝賜教>_<

Tips

• 自定義sort函數(shù)的排序規(guī)則
• 在O(nlogn)時(shí)間內(nèi)計(jì)算frt數(shù)組的技巧（我不知道）