算法笔记：洛谷 P1108 低价购买
1. 题目核心与难点
- 目标：
1 . 求最长下降子序列（LIS）的长度。
2 . 求达到该长度的不重复方案总数。 - 难点：方案去重。若两条路径数值序列完全一致（例如
10 8 6和另外一组10 8 6），即便位置不同，也只能算一种方案。
2.状态转移的定义
f [ i ] f[i] f[i]：以第 i i i 天价格结尾的最长下降子序列长度。
t [ i ] t[i] t[i]：以第 i i i 天价格结尾且长度为 f [ i ] f[i] f[i] 的不同方案总数。
3. 方案数去重：“同值覆盖”
- 痛点：序列
10 8(a) 8(b) 6，会出现两个10 8 6。 - 观察：如果 p r i c e [ j ] = = p r i c e [ i ] price[j] == price[i] price[j]==price[i] 且 j < i j < i j<i，那么以 j j j 结尾能构成的任何下降子序列，以 i i i 结尾也一定能构成，且 i i i 的位置更靠后，潜力更大。
- 策略：在遍历到 i i i 时，如果发现前面有 j j j 的价格等于 i i i，直接将 t [ j ] t[j] t[j]（方案数）清零。
- 本质：它保证了对于相同的数值，只有最后一次出现的位置才会被计入总方案数，从根源上消灭了重复序列的产生。
