信息
- ID
- 95
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
指数暴力枚举每个机遇选或不选
考虑一个 DP
f(i,j,k) 表示经过 i 次机遇后,aj>ak 的方案数
如何统计答案?
答案就是所有满足 i<j 的 f(m,i,j) 之和
如何转移?
枚举状态 i,j,k,设第 i 次机会是交换 ax 和 ay
若 x,y 和 j,k 完全不同,则 f(i,j,k)=2×f(i−1,j,k)
若 x=j,y=k,则 f(i,j,k)=f(i−1,x,k)+f(i−1,y,k),f(i,k,j)=f(i−1,k,x)+f(i−1,k,y)
若 x=j,y=k,则 f(i,j,k)=f(i−1,j,k)+f(i−1,k,j)
复杂度 O(n3)
怎么优化?
第一维可以滚动数组。
注意到,每次转移只有 O(n) 个位置不是 ×2,其他 O(n2) 个位置都是 ×2
那么通过这个观察,我们能否优化掉这 O(n2) 个位置的转移呢?
答案是可以的,我们设
g(i,j,k)=2if(i,j,k),这样每次就不需要 ×2 了,最终答案 ×2m 即可
时间复杂度 O(nm)