ECNUOJ 2615 會議安排

會議安排

Time Limit:1000MS Memory Limit:65536KB
Total Submit:451 Accepted:102

Description

科研人員與相關領域的國內外同行進行適時的接觸與充分的交流，對于促進提高他們的科研業務水平，并及時掌握科研動態是十分必要而且重要的。ECNU為了走在科技的前沿，于是決定派遣一些學者出去參加會議。由于這些會議具有不同的級別，因此對于科研人員可能帶來的科研上的促進作用也就可能不同。但是一個學者不能同時參加兩個會議。而且,如果一個學者需要連續參加兩個會議，第二個會議的開始時間要晚于第一個會議的結束時間..
現在給出一些會議的起始時間和終止時間，并給出這些會議對應的促進值，請你計算出一個學者能夠得到的最大的促進值。

Input

第一行為一個整數T,表示測數數據的組數.
每組數據第一行為整數n(1<=n<=300)，代表有n個會議，然后有n行數據,每行給出3個整數s(會議開始時間),t(會議終止時間),w(會議相對應的促進作用).(0<=s<=t<=365,0<w<100)

Output

輸出能夠得到的最大的促進作用。
每組測試數據輸出占一行。

Sample Input

2
3
2 5 5
4 6 4
6 7 10
3
1 2 3
2 4 10
3 10 2

Sample Output

15
10

Source

華東師范大學2009校賽

解題：直接dp好啦，dp[j]表示在j時間內，能夠獲得最大的促進作用是多少，然后類似于01背包，一頓瞎搞

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int dp[maxn];
struct node{
    int s,t,w;
    bool operator<(const node &o) const{
        return t < o.t;
    }
}m[maxn];
int main(){
    int kase,n;
    scanf("%d",&kase);
    while(kase--){
        scanf("%d",&n);
        for(int i = 0; i < n; ++i){
            scanf("%d %d %d",&m[i].s,&m[i].t,&m[i].w);
        }
        sort(m,m+n);
        memset(dp,0,sizeof dp);
        for(int i = 0; i < n; ++i){
            for(int j = m[n-1].t; j >= 0; --j){
                if(j >= m[i].t) dp[j] = max(dp[j],dp[m[i].s - 1] + m[i].w);
            }
        }
        cout<<dp[m[n-1].t]<<endl;
    }
    return 0;
}

?