题目描述

　　仓库里有一个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

 

输出样例

4

 

题解

　　我们用$f[i]$记录当前取完第$1$至第$(i + 1)$列的物品的最优解，容易得到第$i$个架子有放和不放两种情况，推一下方程即可。

#include 
       
        #define MAX_C 105using 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;}