| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4330 人关注过本帖
标题:偶得一题,序列合并求最优解
只看楼主 加入收藏
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
回复 19楼 xzlxzlxzl
没能理解您压缩矩阵那一步的思想,但您建立的索引列表绝对是非常有用的做法。


图片附件: 游客没有浏览图片的权限,请 登录注册

上面这个测试案例,正确的输出应该是5 1 2 3 4 5  即只在最头部添加一个5就可以使得形成的数据列同时满足前三条子序列的规则。



φ(゜▽゜*)♪
2017-05-02 07:23
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
都说列比较多的时候满足最优解会有很多~而且还是呈几何级别增长趋势~要得出其中一个最优解~得要先遍历所有最优解然后确定其没有其更优解~打算先合并两列来求其最优解~然后递推~不过我验证过了合并两列的最优解不但可能不止一个而且还有可能不在同一个分支~所以我先看看这条题的实现可能性~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-02 07:49
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
我有一个想法,把这道题看作是有向(无权?)图的遍历。每一个输入的分支序列当做一条已知路径,路径上各结点存在对应的有向同路。试计算一个遍历图上各结点的路径(要求每个结点使用次数尽可能少)

我手机没有VPN,去不了谷歌,哪位同仁有空不妨试搜索一下“有向图的遍历相关算法题型”

φ(゜▽゜*)♪
2017-05-02 08:35
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
首先感谢两位的指正!
其实我还是有算法针对20楼和21楼这类数据的,我10楼的代码可得到20楼就版主数据所需的结果,而21楼大神的数据则需要将行列转换后做前排列压缩,选择最短系列即可。
行转换为列的思路以13楼九版主数据为例:
1 2 3 4 5    1 5 1 4 2      1 5 4 2                   1 5 4 2
5 3 2 1 4    2 3 3 2 1 简化 2 3 1    可随意调换顺序   2 1 3   简单拼接
1 3 4 2 5----->3 2 4 1 3----->3 2 4 1------------------>3 2 4 1---------->1 5 4 2 1 3 2 4 1 2 3 4 5
4 2 1 3 5    4 1 2 3 4      4 1 2 3                   1 2 3 4
2 1 3 4 5    5 4 5 5 5      5 4                       4 5
我采取类似我在https://bbs.bccn.net/thread-472197-1-1.html里5楼的递归处理后就可以压缩为正确的9个数字。
看来还是要构思一个通吃的算法,容后提交!
2017-05-02 13:36
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:141
帖 子:1510
专家分:7661
注 册:2014-5-19
收藏
得分:0 
继续关注
2017-05-02 20:38
快速回复:偶得一题,序列合并求最优解
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017693 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved