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

  代码如下:

 #include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = + ; int n,m,r;
struct node
{
int l,r,val;
void read() {scanf("%d%d%d",&l,&r,&val);}
}p[N]; int dp[N];
int dfs(int u)
{
if(dp[u] != -) return dp[u];
int ans = p[u].val;
for(int i=;i<=m;i++)
{
if(p[u].r + r <= p[i].l)
{
ans = max(ans, p[u].val + dfs(i));
}
}
return dp[u] = ans;
} int main()
{
while(scanf("%d%d%d",&n,&m,&r) == )
{
for(int i=;i<=m;i++) p[i].read();
memset(dp,-,sizeof dp);
int ans = ;
for(int i=;i<=m;i++) ans = max(ans, dfs(i));
printf("%d\n",ans);
}
return ;
}

最新文章

  1. iOS,信息加解密
  2. 01.线性表 ArrayList
  3. 为什么springMVC和Mybatis逐渐流行起来了?
  4. Github Bash
  5. 又一款linux提权辅助工具
  6. Sphinx 增量索引更新
  7. 问题:Bringing up interface eth0: Device eth0 does not seem to be present,delaying initialization. [FAILED]—— 找不到网卡。
  8. TortoiseGit上传代码到GitHub
  9. [问题解决] 程序部署到Linux服务器乱码
  10. (八)Index and Query a Document
  11. 利用DNSLOG获取看不到的信息(给盲注带上眼镜)
  12. Dynamics CRM Plug-in
  13. TiKV 源码解析系列——如何使用 Raft
  14. 20145314郑凯杰《网络对抗技术》实验1 逆向及Bof基础实践
  15. SQL Server 字符串合并
  16. JVM内存模型(转载)
  17. 剖析ironic
  18. 【Hutool】Hutool工具类之Http工具——HttpUtil
  19. MANIFEST.MF 文件内容完全详解
  20. Scrapy之CrawlSpider

热门文章

  1. C# 中类的成员有哪些?
  2. eclipse复制工作空间配置步骤
  3. 动态规划-最大算式 蓝桥杯ALGO-116
  4. sql 添加变量
  5. Python UDP 通信
  6. jmeter连接mysql数据库批量插入数据
  7. http上传txt文件
  8. fwrite、write、fread、read
  9. C++ 输出PPM格式图片文件
  10. Selenium(二)开发环境的搭建