poj 2096
题目：
f[ i ][ j ] 表示收集了 i 个 n 的那个、 j 个 s 的那个的期望步数。
#include#include #include #define db doubleusing namespace std;const int N=1005;db n,s,f[N][N];int main(){ scanf("%lf%lf",&n,&s);db ml=n*s; for(int i=n;i>=0;i--) for(int j=s;j>=0;j--) { if(i==n&&j==s)continue; if(i
ZOJ 3329
题目：
高斯消元好像时间复杂度太高。
注意到每个位置都可以从 dp[ 0 ] 转移过来，所以可以想到每个 dp[ i ] 都可以表示成 a[ i ]*dp[ 0 ] + b[ i ] 的形式；这样如果算出了 a[ 0 ] 和 b[ 0 ] ，就能直接算出 dp[ 0 ] 了。
\( dp[i]=a[i]*dp[0]+b[i] \)
\( dp[i]=\sum\limits_{j=1}^{k}dp[i+j]*p[j] + dp[0]*p[0] + 1 \)
\( dp[i]=\sum\limits_{j=1}^{k}(a[i+j]*p[j]*dp[0]+b[i+j]*p[j]) + dp[0]*p[0] + 1 \)
\( dp[i]=((\sum\limits_{j=1}^{k}a[i+j]*p[j])+p[0])dp[0]+(\sum\limits_{j=1}^{k}b[i][j]*p[j])+1 \)
所以 \( a[i]=(\sum\limits_{j=1}^{k}a[i+j]*p[j])+p[0] \) ， \( b[i]=(\sum\limits_{j=1}^{k}b[i][j]*p[j])+1 \)
注意多组数据的清零。空间不是 505 而是 525 。
#include#include #include #define db doubleusing namespace std;int rdn(){ int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret;}const int N=525,M=20;int n,c[5],t[5]; db p[M],a[N],b[N];int main(){ int T=rdn(); while(T--) { n=rdn();for(int i=1;i<=3;i++)c[i]=rdn(); for(int i=1;i<=3;i++)t[i]=rdn(); db tp=1.0/(c[1]*c[2]*c[3]); p[0]=tp; int lm=c[1]+c[2]+c[3]; for(int i=1;i<=lm;i++)p[i]=0;// for(int i=1;i<=c[1];i++) for(int j=1;j<=c[2];j++) for(int k=1;k<=c[3];k++) { if(i==t[1]&&j==t[2]&&k==t[3])continue; p[i+j+k]+=tp; } for(int i=0;i<=n;i++)a[i]=p[0],b[i]=1; for(int i=n+1,j=n+lm;i<=j;i++)a[i]=b[i]=0;//// for(int i=n;i>=0;i--) for(int j=1;j<=lm;j++) a[i]+=a[i+j]*p[j],b[i]+=b[i+j]*p[j]; printf("%.10f\n",b[0]/(1-a[0])); } return 0;}
hdu 4035
题目：
设 f[ i ] 表示现在在 i 号点，期望走几步离开迷宫。
数据范围无法高斯消元。
考虑把 f[ i ] 表示成 a[ i ] * f[ 1 ] + b[ i ] 的形式，这样才能在知道系数之后算出 f[ 1 ] 。它是从 1 号点开始走的，所以应该能表示成这样。
只是这样的话，转移还是没有顺序的。所以考虑把 f[ i ] 表示成 a[ i ] * f[ 1 ] + b[ i ] * f[ fa ] + c[ i ] 的形式。
\( f[i] = k[i]*f[1]+e[i]*0 + \frac{1-k[i]-e[i]}{d[i]}(f[fa]+1) + \frac{1-k[i]-e[i]}{d[i]}\sum\limits_{j \in child}(f[j]+1) \)
\( f[i] = a[i]*f[1]+b[i]*f[fa]+c[i] \) 令 \( s[i]=\frac{1-k[i]-e[i]}{d[i]} \)
\( f[i]=k[i]*f[1]+s[i]*f[fa]+s[i]+(d[i]-1])s[i]+s[i]\sum\limits_{j \in child}(a[j]*f[1]+b[j]*f[i]+c[j]) \)
\( f[i]=k[i]*f[1]+s[i]*f[fa]+d[i]*s[i]+s[i]\sum\limits_{j \in child}a[j]*f[1]+s[i]\sum\limits_{j \in child}b[j]*f[i]+s[i]\sum\limits_{j \in child}c[j] \)
\( (1-s[i]\sum\limits_{j \in child}f[i]=(k[i]+s[i]\sum\limits_{j \in child}a[j])f[1]+s[i]*f[fa]+d[i]*s[i]+s[i]\sum\limits_{j \in child}c[j] \)
答案就是 \( \frac{c[1]}{1-a[1]} \) 。当 \( 1 = a[1] \) 时无解。
精度开成 1e-8 会 WA ， 1e-9 就可以了。
#include#include #include #include #define db doubleusing namespace std;int rdn(){ int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret;}const int N=1e4+5;const db eps=1e-10;int n,hd[N],xnt,to[N<<1],nxt[N<<1],d[N];db k[N],e[N],s[N],a[N],b[N],c[N];void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;d[x]++;}void dfs(int cr,int fa){ db tp=0; for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=fa) { dfs(v,cr);a[cr]+=a[v];c[cr]+=c[v];tp+=b[v]; } a[cr]=a[cr]*s[cr]+k[cr]; b[cr]=s[cr]; c[cr]=c[cr]*s[cr]+d[cr]*s[cr]; tp=1-tp*s[cr]; a[cr]/=tp; b[cr]/=tp; c[cr]/=tp;}int main(){ int T=rdn(); for(int t=1;t<=T;t++) { n=rdn();memset(hd,0,sizeof hd);xnt=0; for(int i=1;i<=n;i++)d[i]=0; for(int i=1,u,v;i