zcmimi's blog
查看原题

点击跳转

f[i]=\max{f[t-r]+p}

#include<bits/stdc++.h>
const int N=1000011;
struct node{int st,ed,p,next;}a[N];
int f[N],head[N];
inline int max(int x,int y){return x>y?x:y;}
int main(){
    int n,m,r;
    scanf("%d%d%d",&n,&m,&r);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&a[i].st,&a[i].ed,&a[i].p);
        a[i].next=head[a[i].ed];
        head[a[i].ed]=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(0,a[i].st-r)]+a[i].p);
    }
    printf("%d\n",f[n]);
}
LG 2889 [USACO07NOV]挤奶的时间Milking-Time
comment评论
Search
search