[CF1542D] Priority Queue 题解

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

我们将这个元素到最小元素的距离称之为这个元素的安全度，则删除最小值后，集合内所有元素的安全度减一；加入

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)

。

code

CPP

#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;
}

[CF1542D] Priority Queue 题解

文章操作

相关推荐

评论

[CF1542D] Priority Queue 题解