POJ 3616 Milking Time

简单DP，感觉就是最长上升子序列的变形

#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=1000+10;
struct X
{
    int St,En,Ef;
} s[maxn];
int n,m,r;
int dp[maxn];

bool cmp(const X&a,const X&b)
{
    if(a.En==b.En) return a.St<b.St;
    return a.En<b.En;
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&r))
    {
        for(int i=0; i<m; i++)
            scanf("%d%d%d",&s[i].St,&s[i].En,&s[i].Ef);
        sort(s,s+m,cmp);
        memset(dp,0,sizeof dp);
        int ans=0;
        for(int i=0; i<m; i++)
        {
            int Max=0;
            for(int j=0; j<i; j++)
                if(s[i].St-s[j].En>=r)
                    Max=max(Max,dp[j]);
            dp[i]=Max+s[i].Ef;
            ans=max(ans,dp[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}