P1108 低价购买【洛谷算法习题】

P1108 低价购买网页链接P1108 低价购买题目描述“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者你必须遵循以下的问题建议:“低价购买再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买再低价购买”的原则。写一个程序计算最大购买次数。这里是某支股票的价格清单日期 1 2 3 4 5 6 7 8 9 10 11 12 价格 68 69 54 64 68 64 70 67 78 62 98 87 \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline \textsf{日期} 1 2 3 4 5 6 7 8 9 10 11 12 \cr\hline \textsf{价格} 68 69 54 64 68 64 70 67 78 62 98 87 \cr\hline \end{array}日期价格​168​269​354​464​568​664​770​867​978​1062​1198​1287​​最优秀的投资者可以购买最多4 44次股票可行方案中的一种是日期 2 5 6 10 价格 69 68 64 62 \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textsf{日期} 2 5 6 10 \cr\hline \textsf{价格} 69 68 64 62 \cr\hline \end{array}日期价格​269​568​664​1062​​输入格式第一行共一个整数N ( 1 ≤ N ≤ 5000 ) N\ (1 \le N \le 5000)N(1≤N≤5000)股票发行天数。第二行一行N NN个整数是每天的股票价格。保证是大小不超过2 16 2^{16}216的正整数。输出格式输出共一行两个整数分别为最大购买次数和拥有最大购买次数的方案数数据保证 $ \le 2^{31}$当二种方案“看起来一样”时就是说它们构成的价格队列一样的时候,这2 22种方案被认为是相同的。输入输出样例 #1输入 #112 68 69 54 64 68 64 70 67 78 62 98 87输出 #14 2解题思路本题核心是动态规划求解最长严格下降子序列长度与去重方案数适配股票低价购买的规则。定义f[i]为以第i天价格结尾的最大购买次数t[i]为对应方案数初始值均为1。通过双重循环遍历若前序价格更高则更新最长长度与方案数题目要求相同价格序列视为同一种方案因此遇到相同价格时将前序状态置零实现去重。遍历完成后取全局最大购买次数累加对应方案数得到最终结果。算法时间复杂度O ( n 2 ) O(n^2)O(n2)完美适配n ≤ 5000 n \le 5000n≤5000的数据范围精准满足去重统计要求。总结核心逻辑动态规划求解最长严格下降子序列同步统计方案数去重处理相同价格的重复序列。关键操作状态转移更新最长长度与方案数相同价格置零前序状态实现去重最终汇总答案。效率保障O ( n 2 ) O(n^2)O(n2)复杂度适配题目数据规模逻辑简洁且满足所有约束条件。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N5e310;constll p1e97;constll INF1e18;constll M5e310;ll a[N],f[N],t[N];intmain(){ll n,x1,y0;cinn;for(ll i1;in;i){cina[i];f[i]t[i]1;}for(ll i2;in;i){for(ll j1;ji;j){if(a[j]a[i]){if(f[i]f[j]1)f[i]f[j]1,t[i]t[j];elseif(f[i]f[j]1)t[i]t[j];}if(a[j]a[i])f[j]t[j]0;}xmax(x,f[i]);}coutx;for(ll i1;in;i){if(f[i]x)yt[i];}cout y;return0;}