| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 684 人关注过本帖
标题:2011年百度之星预赛第一题求解(图标排列)
只看楼主 加入收藏
shinan77
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:87
专家分:188
注 册:2010-9-24
结帖率:100%
收藏
 问题点数:0 回复次数:6 
2011年百度之星预赛第一题求解(图标排列)
百度应用平台上有很多有趣的应用,每个应用都由一个开发者开发,每个开发者可能开发一个或多个应用。百度的工程师们想把应用尽可能好的推荐给用户。
 
研究发现,同一个开发者开发的程序的图标有很大的相似性。如果把同一个开发者开发的应用放在一起,用户很快就会厌倦相似的图标,如果把这些图标穿插摆放效果就会好很多。
 
现在工程师想给用户推荐来自m个开发者的n个应用,在推荐的时候这些应用的图标将排成整齐的一行展示给用户,相邻两个图标之间的距离正好是1,工程师们想让这些图标尽可能的穿插摆放。为了衡量穿插摆放的效果,给每个图标定义一个“分离度”,分离度的值是指当前图标和它左边最近的来自同一个开发者的图标之间的距离。如果一个图标左边没有来自同一个开发者的图标,则分离度为0。所有图标穿插摆放效果的值定义为所有图标的分离度之和。
 
已知每个开发者开发的应用个数,请帮助百度的工程师找到图标穿插摆放效果的最大值。
 
输入描述
 
输入的第一行包含两个整数n和m,用一个空格分隔,分别表示应用的个数和开发者的个数。
 
第二行包含m个正整数,相邻两个数之间用一个空格分隔,表示每个开发者开发的应用个数,这些整数之和必然等于n。
 
输出描述
 
输出一个整数,表示图标穿插摆放效果的最大值。
 
样例输入
 
8 3
 
3 3 2
 
样例输出
 
15
 
提示
 
对于20%的数据,n≤ 10;
 
对于40%的数据,n≤ 100。
 
对于100%的数据,1≤ m ≤ n ≤ 100,000
搜索更多相关主题的帖子: 用户 开发者 工程师 百度应用 
2011-06-15 23:28
夜叶
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:104
专家分:189
注 册:2011-5-7
收藏
得分:0 
坐沙发等高手指点
2011-06-15 23:56
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
DFS应该可以

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-06-16 17:57
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
直接套公式就可以了  (n-k)*k  k为应用大于2的个数
2011-06-16 18:08
shinan77
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:87
专家分:188
注 册:2010-9-24
收藏
得分:0 
回复 4楼 草狼
这个公式是怎么推导出来的呢

--------将学到的东西为我所用,这才是学习的目的 --------
2011-06-16 22:22
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:0 
如果应用大于两个, 你可以再两端各放一个应用,其余的在中间可以随便你真么安排,
应为最后的最长距离就是两端的距离, 中间是连续的,如果一个的话就插中间。

举个列子吧
4个a,4个b, 4个c
你可以abc....abc然后多于的中间随你怎么插都可以
应为最后的长度就是 a...a....a...a+b...b...b...b+c...c...c...c = a........a+b.......b+c.......c
2011-06-18 15:26
xiangqiu1986
Rank: 2
等 级:论坛游民
帖 子:79
专家分:95
注 册:2011-5-5
收藏
得分:0 
待高手

学无止境!
2011-06-18 15:46
快速回复:2011年百度之星预赛第一题求解(图标排列)
数据加载中...
 
   



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

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