poj 3616 Milking Time動的計画
933 ワード
題意:m個の区間を与え、各区間に1つの値を与え、区間間が重なる可能性がある.間隔がRより大きいいくつかの交差しない区間を選択し、最大の値を求める.
Nの役割が何なのかわからず、ダイレクトDP.
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;
}
}