题目链接点这里
大意是，，给你两个排序算法，让你求排序所需要的期望
期望需要逆推，写出状态转移方程就dfs就好了
#include<cstdio> #include<cstring> #include<iostream> #include<math.h> #include<algorithm> #include<queue> using namespace std; #define MX 111111 #define INF 0x3f3f3f3f3f3f3f3f #define mem(x,y) memset(x,y,sizeof(x)) const int p=100000; typedef long long LL; int n; int head[MX],cnt,idcnt; struct Edge { int nxt,num,id; } E[2*MX]; void Hash_init() { mem(head,-1); cnt=idcnt=0; } int Hash_add(int u,int num) { E[cnt].id=idcnt++; E[cnt].num=num; E[cnt].nxt=head[u]; head[u]=cnt++; return idcnt-1; } int getid(int *a) { int t=0; for(int i=0; i<n; i++) t=t*10+a[i]; for(int i=head[t%p]; ~i; i=E[i].nxt) if(E[i].num==t) return E[i].id; return Hash_add(t%p,t); } int ans; double dp[MX]; double dfs1(int *a) { int t=getid(a); if(dp[t]>0) return dp[t]; if(t==ans) return 0; int cnt=0; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { if(a[min(i,j)]<=a[max(i,j)]) continue; cnt++; swap(a[i],a[j]); dp[t]+=dfs1(a)/(n*n); swap(a[i],a[j]); } dp[t]+=1; dp[t]=dp[t]*n*n/cnt; return dp[t]; } double dfs2(int *a) { int t=getid(a); if(dp[t]>0) return dp[t]; if(t==ans) return 0; int cnt=0; for(int i=0; i<n-1; i++) { if(a[i]<=a[i+1]) continue; cnt++; swap(a[i],a[i+1]); dp[t]+=dfs2(a)/(n-1); swap(a[i],a[i+1]); } dp[t]+=1; dp[t]=dp[t]*(n-1)/cnt; return dp[t]; } void solve(int *a) { mem(dp,0); double ans1=dfs1(a); mem(dp,0); double ans2=dfs2(a); printf("Monty %.6f Carlos %.6f\n",ans1,ans2); } int main() { freopen("input.txt","r",stdin); int _; cin>>_; while(_--) { Hash_init(); scanf("%d",&n); int a[10],b[10]; for(int i=0; i<n; i++) scanf("%d",&a[i]); for(int i=0; i<n; i++)b[i]=a[i]; sort(b,b+n); int cnt=unique(b,b+n)-b; for(int i=0; i<n; i++)a[i]=lower_bound(b,b+cnt,a[i])-b; for(int i=0; i<n; i++) b[i]=a[i]; sort(b,b+n); ans=getid(b); solve(a); } return 0; }