题目链接
题意:
有\(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; }