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

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

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

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

[[it] 本帖最后由 天胖 于 2008-10-8 18:26 编辑 [/it]]

大家可以说说想法呀~
穷举搜索？

晕，不会，
呵呵
。应该是这样，
一行一米。最少爬，那就按1米来吧，
相邻的各二个，用递推算法，步进为2。
这样，看有多少列，算出总和，就是最小高度总和
计算和的。只有一解，典型线性的递推算法。呵呵，瞎说的

动态规划

递推么？
如果出现极端值，无法保证最优化解啊。
动态规划？
我水平不够，不清楚这道题目怎么规划= =呵呵

这道题目作为竞赛的第三道（共五道），不应该如此难啊，
看来还是用贪心好了，极端情况忽略吧。。

用动态规划吧……

动规的话感觉状态不好界定，如果记录每一列的高度的话可能需要100维的数组是不是？

一个长度为100的一维数组足已。
30行代码内可以搞定，如果LZ能提供一些测试数据的话，俺可以写个试试。

能否讲讲思路和状态转移方程？

直接给代码吧：

#include<stdio.h>
#include<string.h>
#define MAX 100
#define max2(a,b)   ((a)>(b)?(a):(b))
#define max3(a,b,c) max2(max2(a,b),c)
#define min2(a,b)   ((a)>(b)?(b):(a))

int res[MAX+1];
int solve(int high[],int len){
    int idx;
    res[1] = high[0];
    res[2] = max2(high[0],high[1]);
    res[3] = max3(high[0],high[1],high[2]);
    for(idx = 4;idx <= len;idx ++){
        res[idx] = max3(high[idx-1],high[idx-2],high[idx-3])+res[idx-3];
        res[idx] = min2(res[idx],high[idx-1]+res[idx-1]);
        res[idx] = min2(res[idx],max2(high[idx-1],high[idx-2])+res[idx-2]);
    }
    return res[len];
}

int main(){
    int high[MAX],col,row,size,idx,x,y;
    scanf("%d%d%d",&row,&col,&size);
    memset(high,0,sizeof(high));
    for(idx = 0;idx < size;idx ++){
        scanf("%d%d",&x,&y);
        high[x] = max2(high[x],y);
    }
    printf("%d\n",solve(high,col));
}

其中solve函数不足15行