前言

---

正題

題目鏈接:https://www.luogu.com.cn/problem/P5299

---

題目大意

有$2n$張牌，

• $n$張強(qiáng)化牌，每張上有一個正整數(shù)$x(x>1)$，如果使用后之后的每一張攻擊牌傷害都會乘上$x$。
• $n$張攻擊牌，每張上有一個正整數(shù)$x$，使用后造成$x$點(diǎn)傷害。

隨機(jī)抽上來$m$張，然后按照最優(yōu)策略打出$k$張的情況下，求所有情況造成的傷害和。

$1\le k\le m\le 2n\le 3000$

---

解題思路

考慮一個最優(yōu)策略是啥，顯然地我們有強(qiáng)化牌肯定優(yōu)先打出，直到打完或者只剩最后一費(fèi)。

因為翻倍至少多一倍的傷害，而我們攻擊牌肯定是從大往小選，所以不可能一張攻擊牌使得傷害翻倍。
先把兩種牌按照數(shù)組從大到小排序
我們可以分為兩種情況討論

• 打出$k?1$張強(qiáng)化牌和一張攻擊牌
• 打出$<k?1$張強(qiáng)化牌和若干張攻擊牌

第一種情況我們設(shè)$f_i$表示選出了$i$張強(qiáng)化牌的所有方案中前$k$張牌乘積的和。
然后枚舉一個在$k?1～m$之間的數(shù)字$i$表示抽到了$i$張強(qiáng)化牌，然后再枚舉攻擊力最大的一張攻擊牌，剩下的方案用組合數(shù)計算即可。

第二種情況比較麻煩，同樣的設(shè)$f_{0,i}$表示抽了$i(i<k)$張強(qiáng)化牌的所有方案中所有牌的乘積和。然后設(shè)$f_{i,j}$表示總共選了$i$張攻擊牌和強(qiáng)化牌，打出了前$k$張強(qiáng)化牌和攻擊牌時所有強(qiáng)化牌乘積的和，$g_{i,j}$則表示造成的傷害和。
然后轉(zhuǎn)移即可。

時間復(fù)雜度：$O(nm)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e4,P=998244353; ll T,n,m,k,a[N],b[N],f[N],g[N],fac[N],inv[N],ans; ll C(ll n,ll m){if(m>n)return 0;return fac[n]*inv[m]%P*inv[n-m]%P; } signed main() {inv[0]=fac[0]=inv[1]=1;for(ll i=2;i<N;i++)inv[i]=P-inv[P%i]*(P/i)%P;for(ll i=1;i<N;i++)fac[i]=fac[i-1]*i%P,inv[i]=inv[i-1]*inv[i]%P;scanf("%d",&T);while(T--){scanf("%lld%lld%lld",&n,&m,&k);ans=0;for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);for(ll i=1;i<=n;i++)scanf("%lld",&b[i]);for(ll i=0;i<=m;i++)f[i]=g[i]=0;f[0]=1;sort(a+1,a+1+n);reverse(a+1,a+1+n);sort(b+1,b+1+n);reverse(b+1,b+1+n);for(ll i=1,x;i<=n;i++)for(ll j=m;j>=1;j--){if(j<k)(f[j]+=f[j-1]*a[i]%P)%=P;else (f[j]+=f[j-1])%=P;}for(ll i=k-1;i<m;i++){for(ll j=1;j<=n;j++)(ans+=f[i]*b[j]%P*C(n-j,m-i-1)%P)%=P;f[i]=0;}for(ll i=1;i<=n;i++){for(ll j=m;j>=1;j--){(f[j]+=f[j-1])%=P;if(j<=k)(g[j]+=g[j-1]+b[i]*f[j-1]%P)%=P;else (g[j]+=g[j-1])%=P;}}printf("%lld\n",(ans+g[m])%P);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P5299-[PKUWC2018]Slay the Spire【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。