POJ 3616 Milking Time ——（记忆化搜索）

　　第一眼看是线段交集问题，感觉不会= =。然后发现n是1000，那好像可以n^2建图再做。一想到这里，突然醒悟，直接记忆化搜索就好了啊。。太蠢了。。

　　代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 const int N = 1000 + 5;
 6 
 7 int n,m,r;
 8 struct node
 9 {
10     int l,r,val;
11     void read() {scanf("%d%d%d",&l,&r,&val);}
12 }p[N];
13 
14 int dp[N];
15 int dfs(int u)
16 {
17     if(dp[u] != -1) return dp[u];
18     int ans = p[u].val;
19     for(int i=1;i<=m;i++)
20     {
21         if(p[u].r + r <= p[i].l)
22         {
23             ans = max(ans, p[u].val + dfs(i));
24         }
25     }
26     return dp[u] = ans;
27 }
28 
29 int main()
30 {
31     while(scanf("%d%d%d",&n,&m,&r) == 3)
32     {
33         for(int i=1;i<=m;i++) p[i].read();
34         memset(dp,-1,sizeof dp);
35         int ans = 0;
36         for(int i=1;i<=m;i++) ans = max(ans, dfs(i));
37         printf("%d
",ans);
38     }
39     return 0;
40 }