P4316 绿豆蛙的归宿
拓扑排序+概率期望
概率期望题一般有两种做题方式：正推，逆推
对于终止状态确定的一般用逆推
对于起始状态确定的一般用正推
- 逆推
这道题中，定义dp数组 \(f_i\) 表示从 \(i\) 到终点的路径长度期望，显然，\(f_n=0\)，可以采取逆推的策略，式子如下：
- 正推
如果定义dp数组 \(f_i\) 表示从1到 \(i\) 的路径长度期望，则 \(f_1=0\)，可以进行正推
然而我不会，逃
P4206 聪聪与可可
奇妙的预处理
因为点数极小，所以可以直接bfs预处理最短路，来预处理聪聪每次往哪里走，然后记忆化搜索每次可可随机走的情况即可
Code
#include<bits/stdc++.h>
#define N 1005
using namespace std;
int n,E,c,m;
int dis[N][N],vis[N][N],step[N][N],v[N][N];
struct edge{
int v,nxt;
}e[N*2];
int head[N],tot,deg[N];
double dp[N][N];
inline void add(int u,int v);
void bfs(int x);
double dfs(int i,int j);
int main(){
cin>>n>>E;
cin>>c>>m;
for(int i=1;i<=E;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
deg[u]++,deg[v]++;
}
memset(dis,0x7f,sizeof(dis));
for(int i=1;i<=n;i++) bfs(i);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int mem=0;
for(int k=head[i];k;k=e[k].nxt){
if(dis[j][e[k].v]<dis[j][mem])
mem=e[k].v;
if(dis[j][e[k].v]==dis[j][mem])
mem=min(mem,e[k].v);
}
step[i][j]=mem;
}
printf("%.3lf",dfs(c,m));
}
inline void add(int u,int v){
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
void bfs(int x){
queue<int> q;
q.push(x);
dis[x][x]=0;
while(!q.empty()){
int u=q.front();q.pop();
vis[x][u]=true;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!vis[x][v]){
vis[x][v]=true;
dis[x][v]=dis[x][u]+1;
q.push(v);
}
}
}
}
double dfs(int i,int j){
if(v[i][j]) return dp[i][j];
v[i][j]=true;
if(i==j) return dp[i][j]=0;
int fir=step[i][j],sec=step[fir][j];
if(fir==j||sec==j) return dp[i][j]=1;
double sum=0;
for(int k=head[j];k;k=e[k].nxt)
sum+=dfs(sec,e[k].v);
sum+=dfs(sec,j);
return dp[i][j]=sum/(double)(deg[j]+1)+(double)1;
}
P1654 OSU!
这道题要维护 \(\sum E(x^3)\)，但明显 \(E(x^3)\ne E(x)^3\)
逐步考虑 \(E(x),E(x^2)\)
考虑状态转移方程
维护三个变量转移即可
Code
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n;
double p,x1,x2,x3;
int main(){
cin>>n;
for(int i=1;i<=n;++i){
scanf("%lf",&p);
x3=x3+(3*x2+3*x1+1)*p;
x2=(x2+2*x1+1)*p;
x1=(x1+1)*p;
}
printf("%.1lf",x3);
}
Red is good
题面：
桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
设dp数组 \(f_{i,j}\) 表示有 \(i\) 个红牌 \(j\) 个黑牌时候的最优期望
\(f_{i,j}\) 可以由 \(f_{i-1,j},f_{i,j-1}\) 推出：
意义为最后一张翻的牌为红牌或黑牌对答案的影响
这道题的关键在于“最优策略”是什么，推状态转移方程的途中可以看出来，如果 \(f_{i,j}<0\) 的话，其实在采取最优策略的情况下已经不能够保证正收益了，所以不拿为上，直接令 \(f_{i,j}=0\)
Code
#include<bits/stdc++.h>
#define N 5005
using namespace std;
int r,b;
double dp[N][N];
int main(){
cin>>r>>b;
for(int i=0;i<=r;i++)
for(int j=0;j<=b;j++){
if(i>0) dp[i][j]+=(double)i/(double)(i+j)*(dp[i-1][j]+1);
if(j>0) dp[i][j]+=(double)j/(double)(i+j)*(dp[i][j-1]-1);
if(dp[i][j]<0) dp[i][j]=0;
}
printf("%.6lf",dp[r][b]-0.0000005);
}