【题解】洛谷P1108 低价购买

题目

洛谷P1108低价购买

题解

此题关键在于计算方案数,如果第i个位置的最长序列长度是由第j个位置更新而来的,则方案数更新方法相同。去重只要当数字相同时,清空其中一个位置的重复信息。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月13日 下午4:04

【小白解析】
此题的第一部分可以理解成求给定数列的最大递减子序列,为非常基础的动态分配问题(或许也是贪心?)。具体解法见第10-16行,基本思路是判断在第i个数字之前的数字j,若j大于i ,则判断当前i能够构成的最大递减子序列与j所能构成的序列长度+1(即接上a[i])的大小,取最大值。
方案数计算反方向剖析上述操作。去重操作判断结尾数字a[i]之前是否有与之相等的a[j]:若存在,说明当前为止(在已遍历完第1~j位数字时),任何a[i]结尾的子序列均可以由a[j]替换,故cnt[i]归零——不需要担心删去了多余的、以a[i]结尾的最长子序列数量:由于题目声明:

当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的

此时所有删去的方案都被cnt[j]保留。第j~i-1位数字成为新的考虑范围。
随后,考察a[i]是否小于a[j],并且a[i]结尾的最长序列是否即是a[j]结尾的最长序列后拼接a[i]而成:

f[i]==f[j]+1&&a[i]<a[j]

(注:更明确地表示为:(f[i]==f[j]+1)&&(a[i]<a[j]))
两者同时满足时表达式为1,则cnt[i]可以继承cnt[j];即以a[i]结尾的方案数与a[j]的完全一致,仅是加上a[i]自己而已。
最后27行,遍历所有cnt[i]成员,若对应的f[i]为最大值ans1,则答案加上cnt[i]。
*切勿尝试每产出一个f[i]就判断一次是否为最大值,不仅剔除不了相同情况,而且亲测无效
**罪恶的资本主义,你的存在又让这世界多了道肯爹题目