竞赛题，求算法、思路
题目：
    仓库里有一个R行C列的物品架子，各行行高均1米，借助一部梯子，可以拿到任意格子里的物品。每次梯子只能靠字某一列上，这是可以拿这列和它相邻两列的物品。但只能拿到你爬到的高度以下所有格子中的物品（包括爬到的高度）。
    现在你已经清楚将要拿的一些物品的位置（即行列坐标），但为了提高效率，希望尽可能少爬梯子，即爬梯子总高度和最小（拿第一行爬1m，依次类推）。

所给数据：行数R,列数C,物品数N和每个物品的位置坐标（行，列）
输出：最小高度和

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

我的问题：
1.请问这道题用什么算法？
2.请问这是一个类型的典型题目吗？如果是，是什么类型呢？

各位，随便说说也好呀~

贪心法呗，每次都优先选取最高的物品，然而这时可以有三个落脚点，然后从这三个选一个可以拿到最多东西的点，然后做记号，再找最高的物品拿，以此类推，这样一定可以在最少的距离拿到最多的东西。

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

其实如果考虑有极端情况，感觉很难完美。
所以我最后还是采取贪心啦。
谢谢你的回答~

问题是，如果这种方法在某个数据上面很难完美，那么针对这个数据，其实就没有完美的方法了……
不过，反正数据量这么小，你枚举也是可以的。

假设有一个数组：
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]]

这个题的数据量可以保证搜索不超时

动态规划

动态规划是看别人写的容易自己写的时候就有点堵的慌。。呵呵