信息学奥赛一本通 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:信息学奥赛一本通 1260:拦截导弹(evd)
下一篇:信息学奥赛一本通 1261:城市交通路网(evd)

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月26日 13时37分26秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

隔行变色java代码_jquery入门—选择器实现隔行变色实例代码 2019-04-21
角标越界 Java_【新人求助】利用占位符操作数据库是总是提示数组角标越界是怎么回事 - Java论坛 - 51CTO技术论坛_中国领先的IT技术社区... 2019-04-21
java类中声明log对象_用于Android环境,java环境的log打印,可打印任何类型数据 2019-04-21
db2与mysql编目_DB2编目、联邦数据库 - Goopand's OS Space - OSCHINA - 中文开源技术交流社区... 2019-04-21
atomikosdatasourcebean mysql_SpringBoot2整合JTA组件实现多数据源事务管理 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
macbook pro 卸载mysql_MacBook Pro全新重装OS X Yosemite 2019-04-21
已达到计算机的连接数最大值无法再同此远程计算机连接_电脑远程访问已达到计算机的连接数最大值怎么办?解决方法很简单... 2019-04-21
mysql表名长度_JavaWeb之MySQL(一) 2019-04-21
mysql服务器语法_Mysql语法 2019-04-21
pdf 模版 汉字和数字_《吉林大学珠海学院毕业论文(设计)模板》(汉字标题版) .pdf... 2019-04-21
python bottle部署_nginx+uwsgi+bottle python服务器部署 2019-04-21