POJ 3616 Milking Time ——(记忆化搜索)
2024-10-06 16:30:51
第一眼看是线段交集问题,感觉不会= =。然后发现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 ;
}
最新文章
- iOS,信息加解密
- 01.线性表 ArrayList
- 为什么springMVC和Mybatis逐渐流行起来了?
- Github Bash
- 又一款linux提权辅助工具
- Sphinx 增量索引更新
- 问题:Bringing up interface eth0: Device eth0 does not seem to be present,delaying initialization. [FAILED]—— 找不到网卡。
- TortoiseGit上传代码到GitHub
- [问题解决] 程序部署到Linux服务器乱码
- (八)Index and Query a Document
- 利用DNSLOG获取看不到的信息(给盲注带上眼镜)
- Dynamics CRM Plug-in
- TiKV 源码解析系列——如何使用 Raft
- 20145314郑凯杰《网络对抗技术》实验1 逆向及Bof基础实践
- SQL Server 字符串合并
- JVM内存模型(转载)
- 剖析ironic
- 【Hutool】Hutool工具类之Http工具——HttpUtil
- MANIFEST.MF 文件内容完全详解
- Scrapy之CrawlSpider