非常感谢各位的回答！
动态规划不来，只有用贪心了，
方法与7楼同。

dp[l][r] = min{dp[l][m-2]+dp[m+2][r]}+w

m为l和r间的任意值，取m-1,m,m+1三列中最高物品的高度作为消耗w.

照着孔明的思想自己写了个，没优化……还是觉得贪心比较简单……

#include <stdio.h>
#include <string.h>

#define N 100

int d[N];
int dp[N][N] = {{0}};

int max(int l, int r)
{
    int m = l++;
    for (; l <= r; l++)
        if (d[m] < d[l]) m = l;
    return d[m];
}

int proc(int l, int r)
{
    int i, m = 0, cur;
    if (l > r) return 0;
    if (dp[l][r]) return dp[l][r];
    if (r - l < 3)
        return dp[l][r] = max(l , r);

    cur = 0x7FFFFFFF;
    for (i = l + 1; i <= r - 1; i++)
    {
        int ndp = proc(l, i - 2) + proc(i + 2, r);
        if (ndp < cur) cur = ndp, m = i;
    }
    return dp[l][r] = cur + max(m - 2, m + 2);
}

int main()
{
    int r, c, n;
    while (scanf("%d %d %d", &r, &c, &n) == 3)
    {
        memset(d, 0, sizeof(d));
        memset(dp, 0, sizeof(dp));
        while (n--)
        {
            int x, y;
            scanf("%d %d", &y, &x);
            if (d[x-1] < y) d[x-1] = y;
        }
        printf("%d\n", proc(0, c - 1));
    }
    return 0;
}

7楼的算法不能得到全局最优解。

假设X[] = {0,3,2,0,4,1,0}

用7楼的算法得出的结果是4+3+1=8

但最优解是3+4=7

[[it] 本帖最后由 安静的小羊 于 2008-10-13 20:32 编辑 [/it]]

LS的数据，我在一开始举给出的贪心法，是可以得到最优解的。LS能不能再找找反例呢？

你的算法也不能得出最优解吧。同样用我上面的数据，这里X[]里的数字既表示这一列物品的个数，也表示最高物品的高度。

怎么不能呢？我的策略是先找到最高的那个元素，然后尝试他周围三个列，这里是0,4,1三个列，当然4，1都可以，然后是第二高的列。0，3，2，这里3和2都可以，那么这样的话，爬的总高度就是4+3=7了啊，的确是最优解嘛……

按照你的算法应该是先取2跟4之间的那个0点，因为这里能拿到6个，1、4两个点只能拿到5个

哦，我明白了，谢谢指正。
看来贪心法的确会有点问题的……
还是孔明的DP比较强啊，哈哈~~~

还有，孔明
dp[l][r] = min{dp[l][m-2] + dp[m+2][r] + w}可以不？我试验了这个公式，貌似也是正确的……虽然效率比你的要低一些……感觉这个公式的DP是可以退化到一般的贪心法的……