首先按照
P
P
P属性排序所有人,按照
P
P
P属性升序顺序选人,则只需要考虑
Q
Q
Q属性的大小关系。
设
D
P
DP
DP状态为
d
p
[
i
]
[
j
]
[
k
]
dp[i][j][k]
dp[i][j][k]
表示前
i
i
i个人中选择
j
j
j个,其中最小的没有被选择的人的
Q
Q
Q属性为
k
k
k的方案数量
考虑第
i
+
1
i+1
i+1个人选或者不选
如
果
k
>
第
i
个
人
的
Q
属
性
d
p
[
i
]
[
j
+
1
]
[
k
]
=
(
d
p
[
i
]
[
j
+
1
]
[
k
]
+
d
p
[
i
−
1
]
[
j
]
[
k
]
)
否
则
d
p
[
i
]
[
j
]
[
k
]
=
(
d
p
[
i
]
[
j
]
[
m
i
n
(
k
,
第
i
个
人
的
Q
属
性
)
]
+
d
p
[
i
−
1
]
[
j
]
[
k
]
)
如果k>第i个人的Q属性\\dp[i][j+1][k]=(dp[i][j+1][k]+dp[i-1][j][k])\\否则\\dp[i][j][k]=(dp[i][j][min(k,第i个人的Q属性)]+dp[i-1][j][k])
如果k>第i个人的Q属性dp[i][j+1][k]=(dp[i][j+1][k]+dp[i−1][j][k])否则dp[i][j][k]=(dp[i][j][min(k,第i个人的Q属性)]+dp[i−1][j][k])
#include<bits/stdc++.h> #define ll long long using namespace std; struct Stu { int p,q; bool operator <(const Stu &ths)const { return p<ths.p; } }stu[305]; int dp[305][305][305];//前i个,选了j个,最小的没选的是k的方案数 const int mod=998244353; int main() { int n,K; scanf("%d%d",&n,&K); for(int i=1;i<=n;i++)scanf("%d",&stu[i].p); for(int i=1;i<=n;i++)scanf("%d",&stu[i].q); sort(stu+1,stu+1+n); dp[0][0][n+1]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=i-1;j++) { for(int k=1;k<=n+1;k++) { dp[i][j][min(k,stu[i].q)]=(dp[i][j][min(k,stu[i].q)]+dp[i-1][j][k])%mod; if(k>stu[i].q)dp[i][j+1][k]=(dp[i][j+1][k]+dp[i-1][j][k])%mod; } } // for(int j=0;j<=i;j++) // for(int k=1;k<=n+1;k++)printf("dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k]); } ll ans=0; for(int i=1;i<=301;i++)ans=(ans+dp[n][K][i])%mod; printf("%lld",ans); return 0; }