Bag of mice
题意：有w只白鼠和b只黑鼠，公主和龙轮流抓老鼠，其中龙每抓一只老鼠就会有一只未被抓住的老鼠逃走，先抓到一只白鼠的获胜，问公主获胜的概率是多少
Solution
令dp[i][j]表示还剩i只白鼠和j只黑鼠时公主获胜的概率
如果公主直接抓住一只白鼠，获胜的概率是
\[\frac{i}{i+j} \]如果公主先抓住的是黑鼠，龙抓住的是黑鼠，漏掉了一只白鼠的概率是
\[\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{i}{i+j-2} \]如果公主先抓住的是黑鼠，龙抓住的是黑鼠，漏掉了一只黑鼠的概率是
\[\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{j-2}{i+j-2} \]转移的时候从下往上转移即可
double dp[1005][1005];
void solve()
{
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++)dp[0][i]=0;
for(int i=1;i<=n;i++)dp[i][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=(i*1.0)/(i+j);
if(j>2)dp[i][j]+=(j*1.0)/(i+j)*(j-1.0)/(i+j-1.0)*(j-2.0)/(i+j-2.0)*dp[i][j-3];
if(j>1&&i>0)dp[i][j]+=(j*1.0)/(i+j)*(j-1.0)/(i+j-1.0)*(i*1.0)/(i+j-2.0)*dp[i-1][j-2];
}
}
cout<<fixed<<setprecision(9)<<dp[n][m]<<"\n";
}
换教室
题意：有2n个课程，在一条的时间段上有n个时间点，其中每一个时间点会有2个内容相同但是开课地点不同的课程，有m次修改课程机会，修改是有概率成功的，问期望的花费路程最小值是多少
Solution
令dp[i][j][0/1]表示当前是第i个课程/时间点，包括当前这个已经用了j次修改，当前修改或者不修改课程的期望路程花费
那么dp[i][j][0]可以从dp[i-1][j][0]和dp[i-1][j][1]转移过来，同理dp[i][j][1]可以从dp[i-1][j-1][0]和dp[i-1][j-1][1]转移过来
用floyd把最短路程给处理出来，记得要把自己到自己的路程在floyd后变为0
void solve()
{
int n,m,v,e;cin>>n>>m>>v>>e;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
dp[i][j][0]=dp[i][j][1]=1e9;
}
}
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
{
f[i][j]=f[j][i]=1e9;
}
}
for(int i=1;i<=n;i++)cin>>v1[i];
for(int i=1;i<=n;i++)cin>>v2[i];
for(int i=1;i<=n;i++)cin>>v3[i];
for(int i=1;i<=e;i++)
{
int x,y,z;cin>>x>>y>>z;
f[x][y]=min(z,f[x][y]);
f[y][x]=min(z,f[y][x]);
}
for(int k=1;k<=v;k++)
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<i;j++)
{
if(f[i][j]>f[i][k]+f[k][j])f[i][j]=f[j][i]=f[i][k]+f[k][j];
}
}
}
for(int i=1;i<=v;i++)f[i][i]=0;
dp[1][0][0]=dp[1][1][1]=0.0;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=min(i,m);j++)
{
dp[i][j][0]=min(dp[i-1][j][0]*1.0+f[v1[i-1]][v1[i]],dp[i-1][j][1]+f[v2[i-1]][v1[i]]*v3[i-1]+f[v1[i-1]][v1[i]]*(1-v3[i-1]));
//cout<<dp[i-1][j][1]<<" "<<f[v2[i-1]][v1[i]]*v3[i-1]<<" "<<f[v1[i-1]][v1[i]]*(1-v3[i-1])<<"\n";
if(j>0)
{
dp[i][j][1]=min(dp[i-1][j-1][0]+f[v1[i-1]][v2[i]]*v3[i]+f[v1[i-1]][v1[i]]*(1.0-v3[i]),dp[i-1][j-1][1]+f[v1[i-1]][v1[i]]*(1.0-v3[i-1])*(1.0-v3[i])+f[v1[i-1]][v2[i]]*v3[i]*(1.0-v3[i-1])+f[v2[i-1]][v1[i]]*v3[i-1]*(1.0-v3[i])+f[v2[i-1]][v2[i]]*v3[i-1]*v3[i]);
}
//cout<<dp[i][j][0]<<" "<<dp[i][j][1]<<"\n";
}
}
double ans=1e9;
for(int i=0;i<=m;i++)ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
cout<<fixed<<setprecision(2)<<ans<<"\n";
}