洛谷 P1108 低价购买题解

洛谷：低价购买

1. 题目核心与难点

• 目标：
  1. 求最长下降子序列（LIS）的长度。
  2. 求达到该长度的不重复方案总数。
• 难点：方案去重。若两条路径数值序列完全一致（例如 10 8 6 和另外一组 10 8 6），即便位置不同，也只能算一种方案。

2. 状态转移的定义

• f[i]：以第 i 天价格结尾的最长下降子序列长度。
• t[i]：以第 i 天价格结尾且长度为 f[i] 的不同方案总数。

3. 方案数去重：'同值覆盖'

• 痛点：序列 10 8(a) 8(b) 6，会出现两个 10 8 6。
• 观察：如果 price[j] == price[i] 且 j < i，那么以 j 结尾能构成的任何下降子序列，以 i 结尾也一定能构成，且 i 的位置更靠后，潜力更大。
• 策略：在遍历到 i 时，如果发现前面有 j 的价格等于 i，直接将 t[j]（方案数）清零。
• 本质：它保证了对于相同的数值，只有最后一次出现的位置才会被计入总方案数，从根源上消灭了重复序列的产生。