某道noip模拟题

出处不明(其实在某本书上看过但是忘记出自哪里了),提交方法不明,标题不明

题面

找出符合下面条件的序列a[]个数:

长度为n

  1. 对于第i个位置的数,如果第i+2个位置存在于数列中,那么a[i]<a[i+2]
  2. 对于第i个位置,如果第i+3个位置存在于数列中,那么a[i]<a[i+3]

对于所有1<=i<=n,1<=a[i]<=1000

数列中允许相同数字

数据范围:n<=1000

SOL

主席看到这题就说大概就是很显然一个高维dp但是转移可以均摊O(1)之类之类的...

但是事实这题还是比较复杂的

首先考虑O(n^4)的dp……f[i][a][b][c]……i个数,最后三个是a,b,c的数列个数……转移状态非常显然……不说了……

=-=如果直接优化这个dp……我也没什么办法……

所以我们来挖掘性质……

主席发现:

对于第i个位置的数,如果第i+2个位置存在于数列中,那么a[i]<a[i+2]

对于第i个位置,如果第i+3个位置存在于数列中,那么a[i]<a[i+3]

其实这个等价于

对于第i个位置(i>=3),a[i]比所有a[j]都要大(1<=j<=i-2)……

为什么呢……

于是就可以看到a[i]比所有a[j]都要大(1<=j<=i-2)……

而显然的,当a[i]比所有a[j]都要大(1<=j<=i-2)时……这就是个符合条件的数列

这个性质可以让我们得到另一种dp的状态表示与递推方法f[i][a][b]——表示i个数,前i-2个数的最大值为a,第i-1个数为b的方案数……

怎么递推?

f[i+1][max(a,b)][z]=∑f[i][a][b]……(z>a)

这显然可以用一些技巧做到转移O(1)……然后我们就得到了一个O(n^3)的dp……

..这个思路还能优化吗?

答案是可以的……

考虑换一种状态描述:

f[i][j]表示前i个数,出现的数字最大为j

我们枚举第i个数的大小来完成转移,

首先假设第i个数的大小为k,那么

  1. 如果第i-1个数小于k……因为前i-2个数小于第i个数,所以这种情况对 f[i][j]的贡献为f[i-1][k-1]
  2. 如果第i-1个数大于等于k……显然前i-2个数只要小于k,就会有前i-3个数小于第i-1个数,所以这种情况对f[i][j]的贡献为f[i-2][k-1]*(j-k+1)(第i-1个数的取值有j-k+1种可能)……

那么dp方程就是:

所以我们就能过通过这题的最大数据了——n=1000

但是……我们能不能做得更好呢?

主席说他在找这个数列的生成函数……我表示太弱……啥都不知道……

由于这题的数字上限给定……所以目测oeis上也不会有?

谁要是知道O(n^2)时间复杂度以下的做法的话……请联系我!

Comments

comments powered by Disqus