dp20代码求调,#7、#5是对的
查看原帖
dp20代码求调,#7、#5是对的
516714
zren6ing楼主2023/7/5 08:49
#include <bits/stdc++.h>
using namespace std;
const int maxm=10010;
int N, M, E;
struct Cow{
    int begin, end, pay;
} cow[maxm];
int dp[maxm];
int first[86401], next_[maxm];
int main(){
    cin >> N >> M >> E;
    for (int i=1;i <=N; i++) cin >> cow[i].begin >> cow[i].end >> cow[i].pay;
    memset(first,0,sizeof(first));
    memset(next_,0,sizeof(next_));
    for (int i=1;i <= N; i++){
        next_[i] = first[cow[i].end+1];
        first[cow[i].end+1] = i;
    }
    memset(dp,0,sizeof(dp));
    for (int i=1;i <= E+1; i++){
        if (i-1 >= M) dp[i] = dp[i-1];
        int j = first[i];
        while (j > 0){
            if (cow[j].begin <= i-1 && cow[j].end >= i-1)
                dp[i] = max(dp[i], dp[cow[j].begin] + cow[j].pay);
            else
            	dp[E+1]=-1;
            j = next_[j];
        }
    }
    cout << dp[E+1] << endl;
    return 0;
}
2023/7/5 08:49
加载中...