滑雪场升降轨道建设问题动态规划解题思路及标程

滑雪场升降轨道建设问题动态规划解题思路及标程/n/n### 问题描述/n/n建造滑雪场的升降轨道。起点和终点的高度已知，x坐标分割成若干份，间隔为1，每一点都给出支架的高度。要选择尽可能少的支架顶端建立固定点，两个固定点之间用一条直钢轨连接，要求中间支架的高度都不能超过钢轨在那里的高度。而且两个相邻固定点之间的距离（x坐标的差值）不能超过给定的K。/n/n### 输入格式/n/n第一行是NN和KK，2≤N≤50002≤N≤5000；1≤K≤N-11≤K≤N−1；/n接下来NN行，按顺序给定支架的高度hh，0≤h≤10000000000≤h≤1000000000；/n/n### 输出格式/n/n一个整数，表示最少要选择几个固定点。第一个（起点）和最后一个（终点）一定是固定点。/n/n### 输入数据 1/n/n13 4/n0/n1/n0/n2/n4/n6/n8/n6/n8/n8/n9/n11/n12/n/n### 输出数据 1/n/n5/n/n### 样例解释/n/n5个点为：1，5，7，9，13/n/n### 数据规模/n/n对于30/%30%的数据：N≤2000；K≤30≤N-1N≤2000；K≤30≤N−1；/n/n对于100/%100%的数据：N≤5000；1≤K≤N-1N≤5000；1≤K≤N−1；/n/n### 题目分析/n/n本题是一道经典的动态规划问题，要求选择尽可能少的固定点，使得任意两个固定点之间的距离不超过 'K'，且中间支架的高度都不能超过钢轨在那里的高度。/n/n首先明确一下问题的状态转移方程：/n/n设 'dp[i]' 表示到第 'i' 个支架时选择的固定点数目的最小值，则有：/n/n$$//dp[i] = //min//left//{dp[j]+1//right//}(j<i,x_i-x_j//le K,h_j//ge h_i)$$/n/n其中，'dp[j]+1' 表示在第 'j' 个支架处选择一个固定点，然后从 'j' 到 'i' 的这一段距离就可以用一根钢轨连接起来，而且这根钢轨高度不超过 'h_j' 。/n/n那么问题就转化成了求在 'dp[1],dp[2],//cdots,dp[N]' 中的最小值。最后的答案即为 'dp[N]' 。/n/n### 标程/n/ncpp/n#include <iostream>/n#include <algorithm>/nusing namespace std;/n/nconst int MAXN = 5005;/nint n, k, h[MAXN], dp[MAXN];/n/nint main() {/n cin >> n >> k;/n for (int i = 1; i <= n; i++) {/n cin >> h[i];/n }/n dp[1] = 1;/n for (int i = 2; i <= n; i++) {/n dp[i] = dp[i - 1] + 1;/n for (int j = i - 1; j >= max(1, i - k); j--) {/n if (h[j] >= h[i]) {/n dp[i] = min(dp[i], dp[j] + 1);/n }/n }/n }/n cout << dp[n] << endl;/n return 0;/n}/n/n