poj 3616 Milking Time動的計画


題意:m個の区間を与え、各区間に1つの値を与え、区間間が重なる可能性がある.間隔がRより大きいいくつかの交差しない区間を選択し、最大の値を求める.
Nの役割が何なのかわからず、ダイレクトDP.
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1100
using namespace std;

struct node
{
    int s,t,v;
}a[N];

int d[N];

bool cmp(node a,node b)
{
    return a.s<b.s;
}

int main()
{
    int n,m,r;
    while(~scanf("%d%d%d",&n,&m,&r))
    {
        for(int i=0;i<m;i++)    scanf("%d%d%d",&a[i].s,&a[i].t,&a[i].v);
        sort(a,a+m,cmp);
        memset(d,0,sizeof(d));
        int ans=0;
        for(int i=0;i<m;i++)
        {
            d[i]=a[i].v;
            for(int j=0;j<i;j++)
                if(a[i].s>=a[j].t+r)
                    d[i]=max(d[i],d[j]+a[i].v);
            ans=max(ans,d[i]);
        }
        cout<<ans<<endl;
    }
}