题意：有n项任务，有0.5的概率以时间t[i]做完第i项任务，同时有0.5的概率以时间t[i]+1做完第i项任务。在时间T内依次做这些任务，问做完任务数量的期望值。
思路：设sum为前i件任务所需的时间t之和，当做到第i件任务时
若T-sum>=i，则任务i一定能完成，期望+1。
若T-sum<0，则时间已用尽，退出。
若0<=T-sum<i，则在前i项任务中可能有j项任务的花费时间要多出1，0<=j<=T-sum，
可知有C(i,j)种方案，只要再总方案数除以2i就是概率。期望就是∑C(i,j)/2i，0<=j<=T-sum，
对于每个i计算组合数，总复杂度为O(n2)，考虑如何优化。
可以发现对于所有0<=T-sum<i的情况，T-sum是随着i增加单调递减的。
对于组合数，有C(n+1,k+1)=C(n,k+1)+C(n,k)
于是∑C(n+1,i)=C(n,m)+C(n,m-1)+C(n,m-1)+C(n,m-2)+......+C(n,1)+C(n,0)+C(n,0)，0<=i<=m
即∑C(n+1,i)=C(n,m)+2*∑C(n,j)，0<=i<=m，0<=j<=m-1
于是每次对于i计算方案分为两部分，第一部分有∑C(i,j)+C(i,T-sum[i-1]+1)=C(i-1,T-sum[i-1]+1)+2*∑C(i-1,j)，0<=j<=T-sum[i-1]，可直接由上一层推出
只需再计算并减去第二部分∑C(i,j)，T-sum[i]+1<=j<=T-sum[i-1]+1，即可。复杂度为O(n)。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int maxn=200005; const int mod=1e9+7; ll fac[maxn],inv[maxn],t[maxn]; ll qpow(ll x,ll k,ll p) { ll re=1; while (k) { if (k&1) re=re*x%p; k>>=1; x=x*x%p; } return re; } void prework(int lim) { fac[0]=1;inv[0]=1; for (int i=1;i<=lim;i++) { fac[i]=fac[i-1]*i%mod; inv[i]=qpow(fac[i],mod-2,mod); } } ll get_c(int n,int m) { if (n<m) return 0; return fac[n]*inv[m]%mod*inv[n-m]%mod; } int main() { ll i,j,n,T,now,ans=0; ll inv_two,two,sum; scanf("%lld%lld",&n,&T); prework(n); inv_two=qpow(2,mod-2,mod); for (i=1;i<=n;i++) scanf("%lld",&t[i]); now=1;sum=0; for (i=1;i<=n;i++) { now=now*2%mod; sum+=t[i]; if (T-sum+t[i]+1<=i-1) now+=get_c(i-1,T-sum+t[i]+1); if (T-sum<0) break; else if (T-sum>=i) ans++; else { for (j=T-sum+1;j<=min(T-sum+t[i]+1,i);j++) now=(now-get_c(i,j)+mod)%mod; two=qpow(inv_two,i,mod); ans=(ans+now*two%mod)%mod; } } printf("%lld ",ans); return 0; }
E HDU 4035
题意：给出一个有n个节点的树形迷宫。在i节点，有ki的概率回到节点1，ei的概率走出迷宫，(1-ki-ei)的概率走到与节点i相邻的节点（走到每个节点的概率相同）。问从节点1开始，走出迷宫需要经过的道路数的期望值。
思路：假设E[i]为从节点i开始走出迷宫需要经过的道路数的期望值。
对于叶子节点，
E[i] = ki*E[1]+ei*0+(1-ki-ei)*(E[fa[i]]+1)
= ki*E[1]+(1-ki-ei)*E[fa[i]]+(1-ki-ei)
对于非叶子节点，假设节点i有num个相邻节点（子节点+父节点），
E[i] = ki*E[1]+ei*0+(1-ki-ei)/num*((E[fa[i]]+1)+∑(E[child[i]]+1))
= ki*E[1]+(1-ki-ei)/num*E[fa[i]]+(1-ki-ei)/num*∑E[child[i]]+(1-ki-ei)
假设对于每个节点有E[i]=Ai*E[1]+Bi*E[fa[i]]+Ci
假设i的子节点为j，则∑E[child[i]]=∑E[j]=∑(Aj*E[1]+Bj*E[i]+Cj)
带入式子可知，对于非叶子节点，有
Ai=(ki+(1-ki-ei)/num*∑Aj) / (1-(1-ki-ei)/num*∑Bj)
Bi=(1-ki-ei)/num / (1-(1-ki-ei)/num*∑Bj)
Ci=((1-ki-ei)+(1-ki-ei)/num*∑Cj) / (1-(1-ki-ei)/num*∑Bj)
对于叶子节点，则有
Ai=ki
Bi=1-ki-ei
Ci=1-ki-ei
然后从叶子节点开始往上推就可以了。
由于E[1]=A1*E[1]+C1，所以E[1]=C1/(1-A1)，这就是答案。若A1==1则无答案（由于是浮点数，fabs(A1-1)<1e-9）。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn=10005; const double eps=1e-9; int num,last[maxn],to[maxn<<1],nxt[maxn<<1]; double k[maxn],e[maxn]; double a[maxn],b[maxn],c[maxn]; void add(int x,int y) { to[++num]=y; nxt[num]=last[x]; last[x]=num; } void dfs(int u,int pre) { int i,v,cnt=0; double suma=0,sumb=0,sumc=0; for (i=last[u];i;i=nxt[i]) { v=to[i]; cnt++; if (v==pre) continue; dfs(v,u); suma+=a[v]; sumb+=b[v]; sumc+=c[v]; } double tmp=1-k[u]-e[u]; if (!cnt) { a[u]=k[u]; b[u]=tmp; c[u]=tmp; } else { double dv=1-tmp*sumb/cnt; a[u]=(k[u]+tmp*suma/cnt)/dv; b[u]=tmp/cnt/dv; c[u]=(tmp+tmp*sumc/cnt)/dv; } } int main() { int i,t,n,T,x,y; scanf("%d",&T); for (t=1;t<=T;t++) { num=0; memset(last,0,sizeof(last)); scanf("%d",&n); for (i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } for (i=1;i<=n;i++) { scanf("%lf%lf",&k[i],&e[i]); k[i]/=100; e[i]/=100; } printf("Case %d: ",t); dfs(1,0); if (fabs(1-a[1])<eps) printf("impossible "); else printf("%.6lf ",c[1]/(1-a[1])); } return 0; }
G HDU 2089
比较典型的区间DP
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int a[10],dp[10][2]; int dfs(int pos,int pre,int sta,int lim) { if (!pos) return 1; if (!lim && dp[pos][sta]!=-1) return dp[pos][sta];//记忆化 int i,up,sst,ans=0; if (lim) up=a[pos];//设置该位的上界 else up=9; for (i=0;i<=up;i++) { if (i==4 || (pre==6 && i==2)) continue; if (i==6) sst=1; else sst=0; if (lim && i==a[pos]) ans+=dfs(pos-1,i,sst,1); else ans+=dfs(pos-1,i,sst,0); } if (!lim) dp[pos][sta]=ans; return ans; } int work(int x) { int cnt=0; while (x) { a[++cnt]=x%10; x/=10; } return dfs(cnt,-1,0,1); } int main() { int n,m; memset(dp,-1,sizeof(dp)); while (scanf("%d%d",&n,&m)!=EOF && (n || m)) { printf("%d ",work(m)-work(n-1)); } return 0; }