一、題目描述：
給定一個(gè)序列 $A$，$A$ 的每一個(gè)元素形如 $+x$ 和 $-$，其中 $x$ 為一個(gè)整數(shù)（$1\le x< 998244353$）。
對(duì)于 $A$ 的一個(gè)子序列 $S$，按如下方式計(jì)算 $S$ 的權(quán)值：
你需要依次遍歷 $S$ 中的元素，并且按照序列維護(hù)一個(gè)小根堆 $T$。
特別的，若 $T$ 中沒(méi)有數(shù)，那么就不進(jìn)行刪除操作。
在遍歷完 $S$ 中的元素后，將小根堆 $T$ 中所有數(shù)的和 $sum$ 算出來(lái)。
$sum$ 即為 $S$ 的權(quán)值。
求 $A$ 中所有子序列 $S$ 的權(quán)值和。對(duì) $998244353$ 取模。
數(shù)據(jù)范圍：$1\le n\le 500$。
二、解題思路：
掌握一個(gè)算貢獻(xiàn)的方法：$\sum_A\sum_{x\in A}=\sum_xx\times \sum_A[x\in A]$
于是我們可以很容易的想到單獨(dú)對(duì)于每個(gè) $+x$ 統(tǒng)計(jì)貢獻(xiàn)。
然后這個(gè)是非常容易計(jì)數(shù) $dp$ 的，設(shè)目前我們枚舉的位置為 $p$。值為 $val$。
$f_{i,j}$ 表示目前枚舉到序列的前 $i$ 個(gè)元素，小根堆中有 $j$ 個(gè)數(shù)字小于 $val$ 的子序列個(gè)數(shù)。
轉(zhuǎn)移很好轉(zhuǎn)移，注意 $i$ 與 $p$ 的相對(duì)位置來(lái)進(jìn)行討論。
相同的數(shù)字大小關(guān)系定一個(gè)標(biāo)準(zhǔn)就行了，比如下標(biāo)小的就視為更小。
單次 $dp$ 時(shí)間復(fù)雜度 $O(n^2)$，總時(shí)間復(fù)雜度 $O(n^3)$。
三、完整代碼：
1 #include<iostream> 2 #define N 510 3 #define mod 998244353 4 #define ll long long 5 #define rep(i,l,r) for(ll i=l;i<=r;i++) 6 using namespace std; 7 ll n,ans; 8 ll f[N][N]; 9 ll op[N],a[N]; 10 void add(ll &u,ll v){ 11 u+=v; 12 if(u>=mod) u%=mod; 13 } 14 ll calc(ll p){ 15 ll val=a[p]; f[0][0]=1; 16 rep(i,1,n) rep(j,0,i) f[i][j]=0; 17 rep(i,1,n){ 18 rep(j,0,i) f[i][j]=f[i-1][j]; 19 if(i<p){ 20 if(!op[i]){ 21 rep(j,0,i) add(f[i][j],f[i-1][j+1]); 22 add(f[i][0],f[i-1][0]); 23 }else{ 24 if(a[i]>val){ 25 rep(j,0,i) add(f[i][j],f[i-1][j]); 26 }else{ 27 rep(j,1,i) add(f[i][j],f[i-1][j-1]); 28 } 29 } 30 }else if(i>p){ 31 if(!op[i]){ 32 rep(j,0,i) add(f[i][j],f[i-1][j+1]); 33 }else{ 34 if(a[i]>=val){ 35 rep(j,0,i) add(f[i][j],f[i-1][j]); 36 }else{ 37 rep(j,1,i) add(f[i][j],f[i-1][j-1]); 38 } 39 } 40 } 41 } 42 ll res=0; 43 rep(i,0,n) add(res,f[n][i]); 44 return res; 45 } 46 signed main(){ 47 ios::sync_with_stdio(false); 48 cin.tie(0); cout.tie(0); 49 cin>>n; 50 rep(i,1,n){ 51 char x; cin>>x; 52 if(x=='+') op[i]=1,cin>>a[i]; 53 } 54 rep(i,1,n) if(op[i]) add(ans,calc(i)*a[i]); 55 cout<<ans<<'\n'; 56 return 0; 57 }
四、寫(xiě)題心得：
復(fù)競(jìng)了，感覺(jué)手好生。只有寫(xiě)點(diǎn)簡(jiǎn)單題找一下感覺(jué)了。
不過(guò)這個(gè)題還是很有意思啊！拜謝 $lsy$ 大佬。省選加油！
浙公網(wǎng)安備 33010602011771號(hào)