NC21726. 王者荣耀
描述
"无论何时何地，都会遵守约定"。"奋力逃吧"。"关于取下敌人性命这件事，也从不失约"。
小懒虫zmx平时最喜欢玩的游戏就是《王者荣耀》，在这款游戏中它也最喜欢百里守约这个英雄。最近，zmx准备冲国服百里，所以它开始练英雄，你有很多个时间段来练习英雄，每个时间段有一个开始时间点和结束时间点，以及可以获得的熟练度。不过现在你可以随意修改任意练习时间段的开始和结束时间点，但是你不能修改时间段的长度和获得的熟练度！由于要学习，你只能在固定时间段玩游戏，问你最多可以获得多少熟练度？
例如：你可以把[2,3），修改为[1,2）或者[3,4）等等，他们的长度都是1。
注意：对于某个时间段，不管你有没有修改，必须练完整个时间段长度才能获得熟练度！
输入描述
第一行，三个整数n,S,T(0<n<=1000,0<S<T<1000)代表n个时间段和你能在[S,T）时间段内玩游戏。
接下来n行，每行三个整数a,b(0<a<b<1000),c(0<c<1e7)，用空格分开，代表时间段起始时间[a,b）和可以获得的熟练度。
输出描述
输出一行，包括一个整数，表示zmx能获得的最大熟练度。
示例1
输入:
3 1 3 1 3 5 2 4 6 4 7 8
输出:
6
示例2
输入:
5 1 5 1 2 1 2 3 2 1 3 3 3 4 2 3 6 4
输出:
7
C++ 解法, 执行用时: 5ms, 内存消耗: 400K, 提交时间: 2022-03-19 21:00:53
#include<iostream>
using namespace std;
int n,s,t; long long dp[1010];
int main()
{
cin>>n>>s>>t;
for(int i=0;i<n;i++)
{
int a,b,c;
cin>>a>>b>>c;
for(int j=t-s;j>=b-a;j--)
dp[j]=max(dp[j],dp[j-(b-a)]+c);
}
cout<<dp[t-s]<<endl;
return 0;
}
C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 624K, 提交时间: 2020-06-06 12:22:27
#include<bits/stdc++.h>
using namespace std;
long long dp[1003];
int main(){
int n,i,S,T,b,e,w,t;
cin>>n>>S>>T;
T=T-S;
while(n--){
cin>>b>>e>>w;
t=e-b;
for(i=T;i>=t;i--){
dp[i]=max(dp[i],dp[i-t]+w);
}
}
cout<<dp[T];
return 0;
}