| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2619 人关注过本帖
标题:高中竞赛题,求算法、思路
只看楼主 加入收藏
天胖
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-8
收藏
 问题点数:0 回复次数:20 
高中竞赛题,求算法、思路
竞赛题,求算法、思路
题目:
    仓库里有一个R行C列的物品架子,各行行高均1米,借助一部梯子,可以拿到任意格子里的物品。每次梯子只能靠字某一列上,这是可以拿这列和它相邻两列的物品。但只能拿到你爬到的高度以下所有格子中的物品(包括爬到的高度)。
    现在你已经清楚将要拿的一些物品的位置(即行列坐标),但为了提高效率,希望尽可能少爬梯子,即爬梯子总高度和最小(拿第一行爬1m,依次类推)。

所给数据:行数R,列数C,物品数N和每个物品的位置坐标(行,列)
输出:最小高度和

补充:
    各个数据都不大,100以内;
    高中联赛水平,请用初级方法^^

我的问题:
1.请问这道题用什么算法?
2.请问这是一个类型的典型题目吗?如果是,是什么类型呢?
搜索更多相关主题的帖子: 高中 算法 竞赛题 思路 
2008-10-08 20:53
天胖
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-8
收藏
得分:0 
各位,随便说说也好呀~
2008-10-09 19:52
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
贪心法呗,每次都优先选取最高的物品,然而这时可以有三个落脚点,然后从这三个选一个可以拿到最多东西的点,然后做记号,再找最高的物品拿,以此类推,这样一定可以在最少的距离拿到最多的东西。

专心编程………
飞燕算法初级群:3996098
我的Blog
2008-10-09 20:08
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
额……或者你三个三个列的计算可以拿到的最多东西的列,然后挨个儿去拿……这两个策略你试试看,我不知道哪个是最优的……不过貌似差不多的样子……

专心编程………
飞燕算法初级群:3996098
我的Blog
2008-10-09 20:09
天胖
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-8
收藏
得分:0 
[bo][un]StarWing83[/un] 在 2008-10-9 20:09 的发言:[/bo]

额……或者你三个三个列的计算可以拿到的最多东西的列,然后挨个儿去拿……这两个策略你试试看,我不知道哪个是最优的……不过貌似差不多的样子……


其实如果考虑有极端情况,感觉很难完美。
所以我最后还是采取贪心啦。
谢谢你的回答~
2008-10-09 20:32
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
问题是,如果这种方法在某个数据上面很难完美,那么针对这个数据,其实就没有完美的方法了……
不过,反正数据量这么小,你枚举也是可以的。

专心编程………
飞燕算法初级群:3996098
我的Blog
2008-10-09 20:36
hoodlum1980
Rank: 2
来 自:浙江大学
等 级:论坛游民
威 望:2
帖 子:289
专家分:23
注 册:2008-2-24
收藏
得分:0 
假设有一个数组:
int x[102];
int sum;相邻三列的和;
int selector;
爬梯总高度height=0;

先扫描一边输入,让x[i]的值 为 列i的 最高物品高度,注意索引0和索引101的位置存为0,架子在1到100之间的索引。

当前最大值:
int current_max=0;

while(1)
{
   for(j=1;j<=100;j++)
   {
      if (x[j]>current_max) current_max=x[j], current_index=j;
    }
   if(current_max==0) break;
   我们遍历最大值附近的三列,看从哪里爬最佳。
   sum=0;
   for(j=current_index-1; j<=current_index+1;j++)
   {
       if(x[j-1]+x[j]+x[j+1]>sum) selector=j,sum= x[j-1]+x[k]+x[k+1];
   }
   height += x[current_index]; 我们决定在selector列爬梯。爬梯高度是current_index列的高度。
   x[selector-1] = x[selector] = x[selector+1]=0; 这个时候这列附近的数据对下次的判断已经不具有参考意义。所以清掉它们。
}

然后输出结果:
printf("%d\n", height);


考虑一些特殊情况,比如输入使得所有x[i]均相等,代码是否能适应等。以上为大体思路,供楼主参考。没有测试过,不一定对。因为没有证明这样选是整体最优解。

[[it] 本帖最后由 hoodlum1980 于 2008-10-12 12:30 编辑 [/it]]
2008-10-12 12:17
子洋虾米
Rank: 1
来 自:哈尔滨市第九中学
等 级:新手上路
帖 子:79
专家分:0
注 册:2008-9-15
收藏
得分:0 
这个题的数据量可以保证搜索不超时

好花来年开,好景依旧在;趁你还年轻,抓紧搞竞赛。
2008-10-12 13:36
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
动态规划

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-10-12 13:53
sunkaidong
Rank: 4
来 自:南京师范大学
等 级:贵宾
威 望:12
帖 子:4496
专家分:141
注 册:2006-12-28
收藏
得分:0 
动态规划是看别人写的容易自己写的时候就有点堵的慌。。呵呵

学习需要安静。。海盗要重新来过。。
2008-10-12 14:13
快速回复:高中竞赛题,求算法、思路
数据加载中...
 
   



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

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