[CF1542D] Priority Queue 题解

aeiouaoeiu · 2025-11-24 17:56:37 · 题解

直接考虑整个集合有点困难，考虑从单个元素入手，计数这个元素在多少种情况中在最终集合里面。

我们将这个元素到最小元素的距离称之为这个元素的安全度，则删除最小值后，集合内所有元素的安全度减一；加入 x 时，所有 >x 的元素安全度加一。（元素值相等时,钦定后加的元素比较大）

有了安全度就可以直接对一个元素 x 进行 dp 计数了。设 f_{i,j} 表示当前考虑到第 i 次操作，x 的安全度为 j 的方案数（若此时还没有进行加入 x 的操作，j 表示假设在此时加入 x，x 的安全度）。

首先有不进行本次操作的情况，即 f_{i,j}\to f_{i+1,j}；对于 \texttt - 操作，转移为 f_{i,j}\to f_{i+1,j-1}，若这个操作在加入 x 之前，则还有转移 f_{i,0}\to f_{i+1,0}；对于 \texttt + 操作，若加入的元素大于 x，则 f_{i,j}\to f_{i+1,j}，否则 f_{i,j}\to f_{i+1,j+1}。最终 x 的贡献为 x\sum f_{n,i}。

对每个 x 进行 dp 即可，时间复杂度 \mathcal{O}(n^3)。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=507,ee=1e18,p=998244353;
ll n,X[maxn],f[maxn][maxn],ans;
char O[maxn];
void ups(ll &a,ll b){a=(a+b>=p)?(a+b-p):(a+b);}
void solve(ll x){
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<=n;j++)if(f[i-1][j]){
            if(i!=x) ups(f[i][j],f[i-1][j]);
            if(O[i]=='-'){
                if(!j&&i>x) continue;
                ups(f[i][max(0ll,j-1)],f[i-1][j]);
            }else{
                if((X[i]<X[x])||(X[i]==X[x]&&i<x)) ups(f[i][j+1],f[i-1][j]);
                else ups(f[i][j],f[i-1][j]);
            }
        }
    }
    for(ll i=0;i<=n;i++) ups(ans,f[n][i]*X[x]%p);
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>O[i];
        if(O[i]=='+') cin>>X[i];
    }
    for(ll i=1;i<=n;i++)if(O[i]=='+') solve(i);
    cout<<ans<<"\n";
    return 0;
}

::::