【动态规划】DP搬运工3

UPD：修了点锅（啊昨天居然写脑抽了）

题目内容

给定两个长度为 \(n\) 的序列，定义 \(magic(A,B)=\sum\limits_{i=1}^n \max(A_i,B_i)\)。

现在给定 \(n，K\) 问有多少对 \((A,B)\) 满足 \(magic(A,B)\geq K\)。

结果 \(\mathrm{mod}\ 998244353\)。

思路

关于数据太水导致特判大法直接AC这件事重评了

关于两重排列，可以将 \(B\) 序列固定为 \(1、2、3\dots n\)，最后方案数乘上 \(n!\) 。因为实际上最后变换的就是每一对的位置。然后考虑填 \(A\) 序列。

设 \(f[i][j][k]\) 表示当前填完了 \(1\) ~ \(i\) 的数，其中有 \(j\) 个数填到了下标为 \(i+1\) ~ \(n\) 的位置，\(k\) 为所有 \(\max\{ a[p],b[p] \}\leq i\) 中 \(\max\{ a[p],b[p] \}\) 的和的方案数。

转移分类讨论：

若将 \(i\) 填到了下标 \(i\) ，则k+=i。
若将 \(i\) 填到了下标小于 \(i\) 的位置，下标 \(i\) 的位置填入了小于 \(i\) 的数，则k+=2*i，j--。
若将 \(i\) 填到了下标小于 \(i\) 的位置，下标 \(i\) 的位置填入了大于 \(i\) 的数，则k+=i。
若将 \(i\) 填到了下标大于 \(i\) 的位置，下标 \(i\) 的位置填入了小于 \(i\) 的数，则k+=i。
若将 \(i\) 填到了下标大于 \(i\) 的位置，下标 \(i\) 的位置填入了大于 \(i\) 的数，则j++。

其中1、3、4是可以合并的，添加方案数就为2*j+1。

然后最后答案为\(\sum_{x\geq K} f[n][0][x]\)

其实你在转移的时候把大于 \(K\) 的都加在 \(K\) 里，就不用再求和了。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn=50+10;

const int Mod=998244353;

int n,K;

long long ans;

int f[maxn][maxn][maxn*maxn];

int main(){

#ifndef LOCAL

    freopen("D.in","r",stdin);

    freopen("D.out","w",stdout);

#endif

    scanf("%d%d",&n,&K);

    f[0][0][0]=1;

    for(int i=1;i<=n;i++)

        for(int j=0;j<=i;j++)

            for(int k=0;k<=K;k++){

                long long G=f[i-1][j][k];

                f[i][j][min(k+i,K)]=(f[i][j][min(k+i,K)]+(2*j+1)*G%Mod)%Mod;//1&3&4

                f[i][j+1][k]=(f[i][j+1][k]+G);//5

                if(j)f[i][j-1][min(k+2*i,K)]=(f[i][j-1][min(k+2*i,K)]+j*j*G%Mod)%Mod;//2

            }

    ans=f[n][0][K];

    for(int i=2;i<=n;i++)

        ans=ans*i%Mod;

    printf("%lld\n",ans);

    return 0;

}

巴特西

【动态规划】DP搬运工3

题目内容

思路

代码

最新文章

热门文章