F - Two Exam(AtCoder Beginner Contest 238)

本文主要是介绍F - Two Exam(AtCoder Beginner Contest 238)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

首先按照 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;
}

这篇关于F - Two Exam(AtCoder Beginner Contest 238)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！