信息学奥赛一本通 1262:挖地雷(evd)
发布日期:2022-01-30 02:41:36
浏览次数:19
分类:技术文章
本文共 971 字,大约阅读时间需要 3 分钟。
【题目描述】
在一个地图上有n个地窖(n≤200),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径,并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖,也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任意一处开始挖地雷,然后沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使他能挖到最多的地雷。【输入】
第一行:地窖的个数;第二行:为依次每个地窖地雷的个数;
下面若干行:
xiyi //表示从xi可到yi,xi<yi。
最后一行为"00"表示结束。
【输出】
k1−k2−…−kv //挖地雷的顺序挖到最多的雷。
【输入样例】
6 5 10 20 5 4 5 1 2 1 4 2 4 3 4 4 5 4 6 5 6 0 0 【输出样例】 3-4-5-6 34 【心得】本质上跟LIS差不多,只不过决策变为相邻且更优! 【AC代码】#include#include #include #include using namespace std;const int N=205;int a[N],b[N][N],c[N],f[N];int main(){ int n,x,y,ma=-1; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; f[i]=a[i]; } while(cin>>x>>y) { if(x==0&&y==0) break; b[x][y]=1; } for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { if(b[i][j]&&f[j]+a[i]>f[i]) { f[i]=f[j]+a[i]; c[i]=j; } } if(f[i]>ma)//记录最值和起点 { ma=f[i]; x=i; } } while(c[x]) { cout< <<'-'; x=c[x]; } cout< < <
转载地址:https://blog.csdn.net/everwide1982/article/details/109787701 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年03月26日 13时37分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
隔行变色java代码_jquery入门—选择器实现隔行变色实例代码
2019-04-21
webpack 入口文件 php,如何实现webpack多入口文件打包配置
2019-04-21
php tire树,Immutable.js源码之List 类型的详细解析(附示例)
2019-04-21
matlab转差频率控制,转差频率控制的异步电机调速系统的研究
2019-04-21
oracle错误1327,Oracle中的PGA监控报警分析(r11笔记第97天)
2019-04-21
php函数内的循环,PHP 循环列出目录内容的函数代码
2019-04-21
oracle树状排序,Oracle树状结构查询
2019-04-21
深度linux内核升级,深度操作系统 2020.11.11 更新发布:内核升级
2019-04-21
sql 拆解函数_SQL入门50题详解(含知识点讲解及代码运行步骤拆解)
2019-04-21
java和python交互 jni_Python基于pyjnius库实现访问java类
2019-04-21
mysql表名长度_JavaWeb之MySQL(一)
2019-04-21
mysql服务器语法_Mysql语法
2019-04-21