2021牛客多校第一场I Increasing Subsequence-期望DP

[传送门][https://ac.nowcoder.com/acm/contest/11166/I]

题意:

一个长为$n$的排列,有两个人轮流从中取数,每一轮中所取的数需要满足如下规则:

  1. 取的数大于之前所有人取的数
  2. 取的数的下标大于取数人之前取的数的下标
  3. 如果有多种取数方案,则随机进行取数
  4. 第一个人第一次取数随机
  5. 如果有人没法再取数,游戏结束

求最后期望能取数多少次。

$N\leq 5000$

Solution:

期望DP,比赛时最后想到了做法但是没写完,晚上调了调就过了。

首先想到一个状态:$f[i][j]$表示当前轮选择了第$i$个位置,前一轮选择了第$j$个位置时,游戏期望还能进行的轮数(包括当前轮)。

现在我们考虑$f[i][j]$这个状态能从哪些地方转移过来,即按照正常的游戏顺序,下一轮该如何选择,按照规则我们知道,下一轮能选择的位置$k$必须满足如下条件:

1.$a[k]>a[i]$

2.$k>j$

设所有满足条件的k的数量为$num$,则转移方程为$f[i][j]=\frac {\sum f[k][i]}{num}+1$

初始状态为$f[maxid][i]=1,f[i][n]=1$,其中$i$为任意数,$maxid$为最大数的下标

最后的答案为$\sum f[i][0]$

因为只需要保证$k>j$,所以$k$和$i$的大小关系不确定,因此按照下标从大到小计算是不行的,可能会统计到还没有计算的状态。因此,为了保证能顺利转移,我们按照$a$数组从大到小排序,按照排序后原本下标的顺序进行计算,这样就可以保证统计到的都是已经计算过的状态了,转移的时候每次需要统计大于$j$的下标中,值大于$a[i]$的所有状态的和,单次转移的复杂度为$O(n)$,倒序枚举$j$,对同一个$i$,用一个$sum$记录之前状态的和可以把单次转移复杂度将为$O(1)$,这样的话总复杂度就为$O(n^2)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p[5010],inv[5010];
struct poss{
int id,v;
}a[5010];
int f[5010][5010],pos[5010];
bool cmp(poss a,poss b)
{
return a.v>b.v;
}
const int mod=998244353;
int fast_pow(int x,int a)
{
int ans=1;
for (;a;a>>=1,x=1ll*x*x%mod)
if (a&1) ans=1ll*ans*x%mod;
return ans;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
a[i].id=i,a[i].v=p[i];
}
sort(a+1,a+1+n,cmp);
for (int i=0;i<=n;i++)
f[a[1].id][i]=1,f[i][n]=1,pos[a[i].v]=i;
for (int i=1;i<=n;i++)
inv[i]=fast_pow(i,mod-2);
for (int i=2;i<=n;i++)
{
int sum=0,num=0;
for (int j=n-1;j>=0;j--)
{
if (p[j+1]>a[i].v)
{
sum+=f[j+1][a[i].id],num++;
if (sum>=mod) sum-=mod;
}
f[a[i].id][j]=(1ll*sum*inv[num]+1)%mod;
}
}
int ans=0;
for (int i=1;i<=n;i++)
ans=(ans+f[i][0])%mod;
printf("%d\n",1ll*(ans)*inv[n]%mod);
}

作者

Fizzmy

发布于

2021-08-06

更新于

2021-08-18

许可协议

评论