题目描述
求给定序列 $A=\{a_1,a_2,…,a_n\}$ 的一个子序列 $A’=\{a_i,a_j,…\}$,要求序列 $A’$ 单调递减并最大化其长度,输出 $A’$ 的最大长度及本质不同的构造方案数。
解法
容易发现本题需要求出原序列的 $LDS$,但与普通 $LDS$ 不同的是,本题需要求出 $LDS$ 的方案数。既然这样,$O(n\log n)$ 的做法显然不再适用。本题的数据范围允许我们使用 $O(N^2)$ 做法,考虑在传统 $LDS$ 的基础上做一些改进。
首先回忆 $O(N^2)$ 求 $LDS$ 的状态转移方程:
$$ f_i=max\{f_j\}+1\space(j < i,a_j > a_i) $$
思考该方程的本质:让每个位置的元素继承大于其自身的前缀中的最优解。
既然 $LDS$ 的长度可以继承,我们或许能找到一种解法,让每一个位置的方案数也可以通过这种方式进行转移。
在 $f_i$ 求解完毕之后,考虑 $i$ 之前的某个位置 $j$,如果 $a_j > a_i$ 且 $f_j+1=f_i$,我们就可以认为 $f_i$ 的最优解是利用 $f_j$ 转移得到的。这样一来,$i$ 位置的方案数自然也可以继承 $j$ 位置的方案数了。
我们把以每个位置结尾构造最长 $LDS$ 的方案数用 $C$ 表示,则可以写出方程:
$$ C_i=\sum^i_{j=1}C_j\space(a_j > a_i,f_i=f_j+1) $$
设得到的 $LDS$ 序列 $A’$ 长度为 $maxl$,则总方案数为:
$$ ans=\sum^n_{i=1}C_i\space(f_i=maxl) $$
另外,由于题目中“如果两种方案的买入日序列不同,但是价格序列相同,则认为这是相同的方案”的限制,若存在 $i$ 之前的某个位置 $j$,满足 $a_j=a_i,f_j=f_i$(这句之前有个小锅,感谢评论区提醒),那么我们需要将 $C_j$ 设为 $0$,以避免重复计数。
至此,本题得到完美解决。
C++ 代码
#include<cstdio>
#include<iostream>
using namespace std;
int n,maxx,ans,C[8170],f[8170],a[8170];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
f[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[j]>a[i])f[i]=max(f[j]+1,f[i]);
}
for(int j=1;j<i;j++){
if(f[j]==f[i]&&a[i]==a[j])C[j]=0;
else if(f[i]==f[j]+1&&a[j]>a[i])C[i]+=C[j];
}
maxx=max(maxx,f[i]);
if(f[i]==1)C[i]=1;
}
for(int i=1;i<=n;i++)
if(f[i]==maxx)ans+=C[i];
printf("%d %d",maxx,ans);
}
厉害👍
有个问题想问一下,去重那部分,只需确保a[j] == a[i] 也能AC,是数据太弱了吗? 还是就是说在遍历计算的时候,只要元素值相同,其LDS长度就必然相同,进而推导出个数方案也是一样?
想了一下子好像确实没啥问题,不过“只要元素值相同,其LDS长度就必然相同”是错的,正确的推导过程是:容易发现此时一定有 $f_i\geq f_j$,由于求的是 $\text{LDS}$,$i$ 后面值小于 $a_i$ 的位置(设为 $k$)转移时令 $f_k=f_i+1$ 一定不会比 $f_k=f_j+1$ 更差,因此后面 $j$ 位置就没有用了,所以去重时令 $c_j=0$ 也没什么影响
这篇写得有点仓促了,欢迎帮忙查错,感激不尽
题解里描述,方案数用
C
表示,那么,是不是题解最后一句描述有些问题?确实有问题,感谢提醒
QwQ