题意：

m个挤奶时间段，每个时间段有一个产奶量，每次产完奶奶牛要休息r分钟，问最多产多少奶。m≤1000，时间≤1000000。

题解：

类似，方程改为f[i]=max(f[i+1],f[range[j].r+range[j].value],j为时刻i开始的产奶时间段)。然而本弱的写法时间和空间复杂度都排倒数，神犇们都是用背包dp的写法（我不会）QAQ

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define maxn 1010 5 #define ll long long 6 #define inc(i,j,k) for(int i=j;i<=k;i++) 7 using namespace std; 8  9 inline int read(){10     char ch=getchar(); int f=1,x=0;11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();13     return f*x;14 }15 struct rg{
   int r; ll w; int n;}; rg rgs[maxn]; ll f[maxn*2000]; int n,m,r,g[maxn*1000],mx;16 int main(){17     n=read(); m=read(); r=read();18     inc(i,1,m){
   int a=read(),b=read(),c=read(); rgs[i]=(rg){b,c,g[a]}; g[a]=i; mx=max(mx,a);}19     for(int i=mx;i>=0;i--){20         f[i]=f[i+1]; for(int j=g[i];j;j=rgs[j].n)f[i]=max(f[i],f[rgs[j].r+r]+rgs[j].w);21     }22     printf("%lld",f[0]); return 0;23 }
       
      
     

 

20160802