摘要：
FJ有MM的时间在NN小时内给贝西挤奶，第二次从Start_ IStarti开始到End_ IEndi结束，你可以得到Eff_ IEffi加仑的牛奶。每次FJ给贝西挤奶后，贝西必须休息RR小时，然后FJ才能开始下一次挤奶。现在，FJ需要你计算贝西在这个NN小时内能生产多少牛奶。输入格式的第一行有三个整数，分别表示N、M、RN、M和R。第M+1行，第i+1行，有三个整型Start_ i、End_ i、Eff_ IStarti、Endi、Eff，描述挤奶时间段。问题解决方案：您可以使用spfa#include＜csdio＞#include˂iostream＞#include˂cmath＞#include˂cstdlib＞#include#include#include typedeflonglong；使用namespacestd；组成N=100005；结构节点{intx，y，z，next；}a[N]；intf[N]，头[N]，N，m，r，xx，yy，zz；intmain（）{freopen；freopen；scanf；for{scanf；a[i].next=head[a[i].y]；head[a[i].y]=i；}for{f[j]=f[j-1]；forf[j]=max；}cout˂˂f[n]；return0；｝
题目描述
Bessie 可以在接下来 NN 个小时内产奶，为了方便，我们把这 NN 个小时 0dots N-10…N−1 编号。
FJ 在这 NN 个小时内有 MM 段时间可以来给 Bessie 挤奶，第 ii 段时间从 Start_iStarti 开始到 End_iEndi 结束，可以得到 Eff_iEffi 加仑牛奶。
每次 FJ 给 Bessie 挤奶之后，Bessie 都要休息 RR 个小时，FJ 才能开始下一次挤奶。
现在，FJ 需要您计算出 Bessie 在这 NN 个小时内最多产多少奶。
输入格式
第一行有三个整数，分别表示 N,M,RN,M,R。
第 2dots M+12…M+1 行，第 i+1i+1 行有三个整数 Start_i,End_i,Eff_iStarti,Endi,Effi，描述一段挤奶的时间。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
12 4 2 1 2 8 10 12 19 3 6 24 7 10 31
输出 #1
43
说明/提示
数据规模与约定
对于全部的测试点，保证 1le Nle 10^61≤N≤106，1le Mle 10^31≤M≤103，1le Start_i<end_ile N1≤Starti<endi≤N，1le Eff_ile 10^61≤Effi≤106。
题解：可以spfa跑最长路或者dp都可
#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=100005; struct node{ int x,y,z,next; }a[N]; int f[N],head[N],n,m,r,xx,yy,zz; int main(){ freopen("2889.in","r",stdin); freopen("2889.out","w",stdout); scanf("%d %d %d",&n,&m,&r); for(int i=1;i<=m;i++){ scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z); a[i].next=head[a[i].y]; head[a[i].y]=i; } for(int j=1;j<=n;j++){ f[j]=f[j-1]; for(int i=head[j];i;i=a[i].next) f[j]=max(f[j],f[max(a[i].x-r,0)]+a[i].z); } cout<<f[n]; return 0; }