仓库里有一个C列（column）R行（row）的放物品的架子。为了能拿到任意格子里的物品，必须使用一个梯子。每次梯子只能靠在一列上，这时可以拿这列和它相邻的两列的物品，但只能拿到你爬到的高度以下的所有格子中的物品（包括爬到的高度）。现在你知道今天将要拿的一些物品的位置（行，列），但为了减少危险，想尽可能少爬梯子，即爬梯子的总高度和最小。
编程求出完成今天任务后，所需爬梯子的最小可能的高度和。
第一行有两个被空格分隔的整数C和R，1≤C≤100，1≤R≤100，分别表示列数和行数；
第二行只有一个整数n，1≤n≤100，表示需要拿的物品的数量；
接下来的n行，每行有两个整数A和B，1≤A≤C，1≤B≤R，表示你拿物品的位置。
一行，你拿到的所有物品后的可能最少爬梯子的高度和。
5 5
3
2 3
3 4
4 4
我们用$f[i]$记录当前取完第$1$至第$(i + 1)$列的物品的最优解，容易得到第$i$个架子有放和不放两种情况，推一下方程即可。
#include <iostream> #define MAX_C 105 using namespace std; int c, r; int n; int a[MAX_C]; int f[MAX_C]; int main() { cin >> c >> r >> n; for(register int x, y, i = 1; i <= n; i++) { cin >> x >> y; a[x] = max(a[x], y); } f[0] = a[1]; f[1] = max(a[1], a[2]); f[2] = max(a[1], max(a[2], a[3])); for(register int i = 3; i <= c; i++) { f[i] = min(f[i - 3] + max(a[i], max(a[i - 1], a[i + 1])), f[i - 1] + a[i + 1]); // 第i列放梯子或不放梯子 } cout << f[c]; return 0; }
原文：https://www.cnblogs.com/kcn999/p/10846122.html
