I-Increasing Subsequence

$f_{i,j,0/1}$表示上一輪第一個人選了$i$，第二個人選了$j$，并且當前是第1/2個人選擇的概率。

轉移考慮枚舉k下一步往哪走
$f_{i,k,1}=\sum f_{i,j,0}/\text{cnt}$

$f_{k,j,0}=\sum f_{i,j,1}/\text{cnt}$

答案是所有數組之和：每進一個新狀態都意味著游戲多進行了一局，因此把出現的概率全部累加就是期望局數。
顯然的暴力~
時間復雜度：$O(n^3)$

Code1

#include<bits/stdc++.h>using namespace std; using ll=long long;const int N=5010; const int mod=998244353;ll f[N][N][2]; ll inv[N]; int a[N],n; ll qmi(ll a,ll b) {ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;for(int i=1;i<=n;i++) inv[i]=qmi(i,mod-2);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++)for(int j=0;j<=n;j++){if(j==0) f[i][j][0]=inv[n];int ct=0;// 第一個人for(int k=j+1;k<=n;k++)if(a[k]>a[i]&&a[k]>a[j]) ct++;for(int k=j+1;k<=n;k++)if(a[k]>a[i]&&a[k]>a[j]) f[i][k][1]=(f[i][k][1]+inv[ct]*f[i][j][0])%mod;// 第二個人ct=0;for(int k=i+1;k<=n;k++)if(a[k]>a[i]&&a[k]>a[j]) ct++;for(int k=i+1;k<=n;k++)if(a[k]>a[i]&&a[k]>a[j]) f[k][j][0]=(f[k][j][0]+inv[ct]*f[i][j][1])%mod;}ll ans=0;for(int i=1;i<=n;i++)for(int j=0;j<=n;j++) ans+=f[i][j][0]+f[i][j][1],ans%=mod;cout<<ans<<'\n';return 0; }

---

沒聽懂講題人上述解法的優化，詢問了mrk大佬的思路。并且參考下面題解，感覺更容易理解lalalzo題解

對于上述做法關鍵是我們需要區分這一步是誰走的，而下面的做法考慮在所給序列的值域上從小到大走，保證了所選必須比前面所有選的值要大，還有一個限制就是對于每一個人的所選序號單增。

設計dp

狀態表示：$f_{u,v}$表示最后一個人選擇$v$而倒數第二個人選擇$u$，值域從小到大走需要滿足$u<v$停下來的期望步數。

狀態轉移：考慮移動一步$f_{u,v}\to f_{v,k}$需要滿足$u<v<k\text{?and?}{\text{pos}}_u<{\text{pos}}_k$
$$f_{u,v}=\frac{1}{\text{cnt}}\sum _k{f}_{v,k}+1$$
發現滿足${\text{pos}}_u<{\text{pos}}_k$意味著每一個人的所選序號單增。非常巧妙啊~

于是有下面Code2常見的記憶化搜索寫法（我之前比較熟悉記憶化搜索）

Code2

#include<bits/stdc++.h> using namespace std; template <class T=int> T rd() {T res=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res; } const int N=5010,mod=998244353; using ll=long long; int pos[N],n; ll inv[N],f[N][N]; ll qmi(ll a,ll b) {ll v=1;while(b){if(b&1) v=v*a%mod;a=a*a%mod;b>>=1;}return v; } // u<v<k ll dfs(int u,int v) {if(f[u][v]!=-1) return f[u][v];// f[u][v] -> f[v][k] u<v<k&&pos[u]<pos[k]int ct=0;for(int k=v+1;k<=n;k++) if(pos[u]<pos[k]) ct++;f[u][v]=(ct>0?1:0);for(int k=v+1;k<=n;k++) if(pos[u]<pos[k]) f[u][v]=(f[u][v]+dfs(v,k)*inv[ct])%mod;return f[u][v]; } int main() {n=rd();for(int i=1;i<=n;i++) pos[rd()]=i;for(int i=1;i<=n;i++) inv[i]=qmi(i,mod-2);memset(f,-1,sizeof f);ll ans=0;for(int i=1;i<=n;i++) ans=(ans+dfs(0,i))%mod;ans=ans*inv[n]%mod;printf("%lld\n",ans);}

Code3

把上面記憶化搜索代碼轉化為迭代（考慮該狀態會對哪些狀態產生貢獻），就有了下面的Code3

#include<bits/stdc++.h> using namespace std; template <class T=int> T rd() {T res=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res; } const int N=5010,mod=998244353; using ll=long long; int pos[N],n; ll inv[N],f[N][N]; ll qmi(ll a,ll b) {ll v=1;while(b){if(b&1) v=v*a%mod;a=a*a%mod;b>>=1;}return v; } int main() {n=rd();for(int i=1;i<=n;i++) pos[rd()]=i;for(int i=1;i<=n;i++) inv[i]=qmi(i,mod-2);// f[k][i] -> f[i][j] k<i<j && pos[k]<pos[j]// f[k][i] +=1/ct f[i][j] + 1for(int i=n;i>=1;i--){for(int k=0;k<i;k++){int ct=0;for(int j=i+1;j<=n;j++) if(pos[j]>pos[k]) ct++;for(int j=i+1;j<=n;j++)if(pos[j]>pos[k])f[k][i]=(f[k][i]+inv[ct]*f[i][j]%mod);if(ct) f[k][i]=(f[k][i]+1)%mod;}}ll ans=0;for(int i=1;i<=n;i++) ans=(ans+f[0][i])%mod;ans=ans*inv[n]%mod;printf("%lld\n",ans);}

Code4

不難發現每次我們想知道${\text{pos}}_k<{\text{pos}}_j$，可以預處理前綴和優化。

#include<bits/stdc++.h> using namespace std; template <class T=int> T rd() {T res=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res; } const int N=5010,mod=998244353; using ll=long long; int pos[N],n; ll sum[N],cnt[N],inv[N],f[N][N]; ll qmi(ll a,ll b) {ll v=1;while(b){if(b&1) v=v*a%mod;a=a*a%mod;b>>=1;}return v; } int main() {n=rd();for(int i=1;i<=n;i++) pos[rd()]=i;for(int i=1;i<=n;i++) inv[i]=qmi(i,mod-2);for(int i=n;i>=1;i--){memset(cnt,0,sizeof cnt);memset(sum,0,sizeof sum);for(int j=i+1;j<=n;j++){cnt[pos[j]]++;sum[pos[j]]=f[i][j];}for(int j=n-1;j>=0;j--){cnt[j]+=cnt[j+1];sum[j]=(sum[j]+sum[j+1])%mod;}for(int k=0;k<i;k++) {int id=pos[k];f[k][i]=(sum[id]*inv[cnt[id]]%mod+1)%mod;}}ll ans=0;for(int i=1;i<=n;i++) ans=(ans+f[0][i])%mod;ans=ans*inv[n]%mod;printf("%lld\n",ans); }

---

總結：

其實對于上述兩種方法有本質的區別就是定義的狀態一個是概率一個是期望步數，需要注意如何定義狀態~

要加油哦~

總結

以上是生活随笔為你收集整理的2021牛客暑期多校训练营1 I-Increasing Subsequence（期望dp+优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。