ARC207A Affinity for Artifacts 题解

· · 题解

设总成本为 w，第 i 个灯是第 p_i 个被点亮的。考虑每个灯节约了多少成本，则显然有：

\left(\sum_{i=1}^n a_i\right)-w=\sum_{i=1}^n \min(a_i,p_i-1)

考虑把 a_i 看作 1 类数，p_i-1 看作 2 类数，将所有 a_i 和所有 p_i-1 扔进一个长度为 2n 的数列 c 中并从大到小排序，每次选出一个 1 类数和 2 类数进行匹配，贡献为较小的数的值。

设 f_{i,j,k} 表示考虑到数列 c 的第 i 项，此时一共匹配了 j 对数，总贡献为 k 的方案数。转移时，首先根据 i,j 和前缀和数组，计算出未匹配的 1 类数数量 x 和未匹配的 2 类数数量 y，再根据 c_{i+1} 的类型分别处理：

初始化 f_{0,0,0}=1。设 v=\left(\sum\limits_{i=1}^n a_i\right)-x，特判一下 v \lt 0 和 v \gt \frac {n(n-1)}2 的情况，答案即为 \sum\limits_{i=v}^{\frac{n(n-1)}{2}} f_{2n,n,i}。

时间复杂度 \mathcal O(n^4)。

const int N=105,mod=998244353;
int n,x,a[N],s[N<<1][3],f[N<<1][N][N*(N-1)/2];
ll sum,v;
pii p[N<<1];
int get(int i,int j){
    int a=s[i][1],b=s[i][2];
    return b-a+j;
}
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    v=sum-x;
    if(v<0) v=0;
    if(v>n*(n-1)/2) v=n*(n-1)/2+1;
    for(int i=1;i<=n;i++) p[i]={a[i],1},p[n+i]={i-1,2};
    sort(p+1,p+n+n+1),reverse(p+1,p+n+n+1);
    for(int i=1;i<=n+n;i++) for(int j=1;j<=2;j++) s[i][j]=s[i-1][j]+(p[i].se==j);
    f[0][0][0]=1;
    for(int i=0;i<n+n;i++){
        for(int j=0;j<=min(s[i][1],s[i][2]);j++){
            int x=s[i][1]-j,y=s[i][2]-j;
            for(int s=0;s<=n*(n-1)/2;s++){
                if(p[i+1].se==1){
                    if(y!=0) add(f[i+1][j+1][s+p[i+1].fi],1ll*f[i][j][s]*y%mod);
                    add(f[i+1][j][s],f[i][j][s]);
                }
                else{
                    if(x!=0) add(f[i+1][j+1][s+p[i+1].fi],1ll*f[i][j][s]*x%mod);
                    add(f[i+1][j][s],f[i][j][s]);
                }
            }
        }
    }
    int ans=0;
    for(int i=v;i<=n*(n-1)/2;i++) add(ans,f[n+n][n][i]);
    cout<<ans<<endl;
}