关于概率期望的更多应用问题(更新中)
1.与方差有关的,可以推导出D(x)=E(x的平方)-E平方(X)
推导过程见下图:(博客园图片太水了,就用的luogu的)
然后就是例题:「重庆市NOIP模拟赛」好路线 (dp)
dp[i][j][k]表示到(i,j)这个点时,前面路径上h的和是k(就相当于美剧了所有路径)此时这条路径上h的平方和最小值
为什么这么设?
E(x)在此时就是E(h),E相当于平均数
那么E(h)=(k/(i+j-1)),两边平方就可以得到公式中的减数
那么dp为什么要存平方和呢?
E(x方)=E(h方)=h平方和的平均数=dp/(i+j-1)
那dp为什么要存最小值呢?因为我枚举k,相当于减数已经确定,让被减数,也就是dp最小的情况下,这样相减得到的答案最小,也就是方差最小了
那最后只需要美剧(dp[n][m][i])就可以了(用上式计算取min即可)
当然最后答案乘上了(n+m-1)的平方,那么就是dp[n][m][i](n+m-1)-ii就是了
附上评测链接(bz的才有福利哦)
http://222.180.160.110:1024/problem/9931
#include<bits/stdc++.h>
using namespace std;
int h[55][55];
int dp[55][55][12505];//走到i,j时,h和(利用这个除以路长度再平方就是E方(x),存的是h方之和的最小值
int main(){
ios::sync_with_stdio(false);
int n,m;
cin >> n >> m;
int ma=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> h[i][j];
ma=max(ma,h[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=ma*(n+m-1);k++){
dp[i][j][k]=0x3f3f3f3f;
}
}
}
dp[1][1][h[1][1]*1]=h[1][1]*h[1][1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=ma*(n+m-1);k++){
if(dp[i][j][k]==0x3f3f3f3f){
continue;//这个状态转移不到
}
int nx=i+1;
int ny=j;
dp[nx][ny][k+h[nx][ny]]=min(dp[nx][ny][k+h[nx][ny]],dp[i][j][k]+h[nx][ny]*h[nx][ny]);
nx=i;
ny=j+1;
dp[nx][ny][k+h[nx][ny]]=min(dp[nx][ny][k+h[nx][ny]],dp[i][j][k]+h[nx][ny]*h[nx][ny]);
}
}
}
int mii=0x3f3f3f3f;
for(int i=0;i<=ma*(n+m-1);i++){
if(dp[n][m][i]==0x3f3f3f3f){
continue;
}
mii=min(mii,(n+m-1)*dp[n][m][i]-i*i);//最后要求求(n+m-1) 的平方乘上他,就可以化简了
}
cout<<mii;
}