NOIP 1999 提高组算法题解

零、背景

今天继续分享 1999 年 NOIP 提高组题解。

一、旅行家的预算

题意：告诉你始发站到终点的距离，以及中间 N 个加油站的位置与油价。
每升油能开的距离是固定的，问是否可以从始发站开到目的地，可以的话最少花费多少钱。

思路：后悔贪心。

基本思路：先把油箱加满，并记录每一滴油的油价。
走一段路，优先消耗油价最低的油。
如果遇到一个加油站，油价更便宜，则把较贵的油都后悔退还，然后购买这个更便宜的油，最后也需要把油箱加满。
到达终点后，剩余的油全部后悔退还。

根据上面的思路，可以发现我们需要一个单调双向队列，来记录每个油价有多少油。
走一段路程时，消耗队列前面便宜的油。
遇到更便宜的加油站时，把队列后面较贵的油后悔退掉。

小技巧：在终点站追加一个油价为 0 的加油站，这样可以在最后把剩余的油全部后悔换成免费的油。

N 个加油站需要排序，排序最占时间。
复杂度：O(n log(n))

二、导弹拦截

题意：爱国者防御导弹有一个缺陷，后面发射的导弹高度不能高于之前发射导弹的高度。
现在告诉你所有入侵导弹的高度，问最多可以拦截多少个导弹。

思路：最长非递减子序列。

直接套 LIS 动态规划模板即可。

LIS 状态定义：dp[i] 标识长度 i+1 的非递减子序列能够取得的最小结尾。
复杂度：O(n log(n))

vector<ll> dp;
dp.reserve(a.size());
for (ll x : a) {
  auto it = upper_bound(dp.begin(), dp.end(), x);
  if (it == dp.end()) {
    dp.push_back(x);
  } else {
    *it = x;
  }
}
return dp.size();

三、邮票面值设计

题意：有 K 种邮票，每种数量无限，最多共选择 N 张，问最大可以得到的面值 M 是多少，使得 [1, M] 之间的每一个数字都可以得到。

思路：搜索+DP。

假设 K 种邮票已经确定，则可以完全背包，来计算最大的 M。
背包大小：N * V
复杂度：O(K * N * V)

如何得到 K 种邮票呢？
由于不知道哪种组合是最优解，只能暴力枚举所有组合。

枚举策略：假设当前枚举了 A 种邮票，枚举到了 B，可以得到的最大值为 AM，则下一个邮票只能从 [B+1, AM+1] 中选择。

B+1 很容易理解，邮票从小到大枚举。
AM+1 解释：前 B 种邮票可以得到 [1,AM]，下个邮票最大不能超过 AM+1，否则就无法构造出 AM+1。

复杂度：O(能过)
注：这道题没有高效的算法，只能暴力枚举。

四、最后

1999 年的 NOIP 提高组的题比较简单，第一道后悔贪心，第二道 LIS 模板题，第三道是搜索题，只能暴力枚举+完全背包。
不看暴力枚举，三个都属于基本的算法了。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code