【学校OJ】 1412.仓库的架子

【动态规划】10.X仓库的架子

【问题描述】
　　仓库里有一个C列( column )R行(row)的放物品的架子。为了能拿到任意格子里的物品，必须使用一个梯子。每次梯子只能靠在一列上，这时可以拿这列和它相邻的两列的物品，但只能拿你爬到的高度以下的所有格子中的物品（包括爬到的高度）。现在你知道今天将要拿的一些物品的位置（行、列），但为了减少危险，想尽可能少爬梯子，即爬梯子的总高度和最小。
　　编程求出完成今天任务后，所需爬梯子的最小可能的高度和。
【输入格式】
　　第1行有两个被空格分隔的整数C和R，1≤ C ≤100，1≤ R ≤100，分别表示列数和行数；
　　第2行只有一个整数n，1≤ n ≤100，表示需要拿的物品的数量；
　　接下来的n行，每行有2个整数A和B，1 ≤ A ≤C，1≤ B ≤R，表示你拿物品的位置。
【输出格式】
　　仅1行，你拿到所有物品后的可能最少爬梯子的高度和。
【输入输出样例】

这道题用区间DP就好了
dp[i]代表前i列的最小值
然后不断更新

#include<iostream>
using namespace std;
int C,R,n,h[100001]={0},dp[100001]={0};//乱开的，不用这么大，别介意
int main(){
	cin>>C>>R;
	cin>>n;
	for(int i=1;i<=n;i++){
		int c,r;
		cin>>c>>r;
		h[c]=max(h[c],r);//最高高度，同列低于最高高度的没有用
	}
	for(int i=1;i<=C;i++){
		if(h[i]==0){//没有任何物品
			dp[i]=dp[i-1];//将前一列状态后移
			continue;
		}
		dp[i]=dp[i-1]+h[i];//假设爬这列的梯子
		if(i==1) continue;//防止越界
		dp[i]=min(dp[i],dp[i-2]+max(h[i],h[i-1]));①
		if(i==2) continue;//防止越界
		dp[i]=min(dp[i],dp[i-3]+max(h[i],max(h[i-1],h[i-2])));②
	}
	cout<<dp[C];
}

方案①判断的这种情况↓

方案②判断的这种情况↓