Gym 103306J John in the Amusement Park（dp）

本文主要是介绍Gym 103306J John in the Amusement Park（dp），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接
题意：
有\(n\)个任务，总时间为\(T\)，从\(0\)开始。每个任务有\(m\)个开始时间\(T_i\)，有一个高兴值\(h\)，持续时间\(t_i\)(每个活动可重复进行，任务活动时间不重叠)，且最后一个任务在\(T\)时间内开始，不必\(T\)时间内结束。
求\(T\)时间内最大高兴值。

思路：
动态规划
\(dp[i]:\)某活动在时刻\(i\)结束，时间\(i\)内最大高兴值，否则为\(0\)。
对于任务\(K\)，开始时间为\(s_k\)，结束时间为\(e_k\)，高兴值为\(w\)，则\(dp[e_k] = max(max(dp[m]+w)，dp[e_k])，m<=s_k\)。
\(ans=max(dp[i])，i<=T\)

code:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <unordered_map>

#define fi first
#define se second
#define pb push_back
#define endl "\n"
#define debug(x) cout << #x << ":" << x << endl;
#define bug cout << "********" << endl;
#define all(x) x.begin(), x.end()
#define lowbit(x) x & -x
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
#define ull unsigned long long
#define ll long long 

const double eps = 1e-15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const int mod =  1e9 + 7;
const int maxn = 1e6 + 10;

using namespace std;

struct node{
    int s, e, h;
    bool operator<(const node &a)const{
        return s < a.s;
    }
}s[maxn];
int dp[maxn], n, t;

int main(){
    scanf("%d%d" ,&n, &t);
    int tot = 0;
    for(int i = 1; i <= n; i ++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        for(int j = 1; j <= c; j ++){
            scanf("%d", &s[++ tot].s);
            s[tot].e = s[tot].s + b, s[tot].h = a;
        }
    }

    sort(s + 1, s + tot + 1);

    int maxx = 0, p = 1;
    for(int i = 0; i <= t; i ++){
        maxx = max(maxx, dp[i]);

        while(p <= tot && s[p].s == i){
            if(s[p].e <= t)dp[s[p].e] = max(dp[s[p].e], maxx + s[p].h);
            else dp[t] = max(dp[t], maxx + s[p].h);
            p ++;
        }
    }

    printf("%d\n", max(maxx, dp[t]));
    return 0;
}

这篇关于Gym 103306J John in the Amusement Park（dp）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！