概率DP和期望DP
admin
2024-03-17 22:14:59
0次

概率DP&期望DP

入门而已啦QAQ

两者好像是属于同一类问题(?

但思路总体恰恰相反:

概率DP:

采用顺推,也就是从初始状态推向结果。

期望DP:

采用逆推,从末状态推向结果。

(可能有点抽象

看几道经典例题吧!

概率DP

1. Bag of mice

思路:

我们分类讨论所有情况,

设 f[i][j]f[i][j]f[i][j]为轮到公主时袋子里有iii 只白鼠,jjj 只黑鼠,公主赢的概率。

初始化边界, f[0][i]=0f[0][i] = 0f[0][i]=0因为没有白鼠了算龙赢, f[i][0]=1f[i][0]=1f[i][0]=1因为抓一只就是白鼠,公主赢。 考虑f[i][j]f[i][j]f[i][j] 的转移:

  • 公主抓到一只白鼠,公主赢了。概率为 ii+j\frac{i}{i + j}i+ji​;
  • 公主抓到一只黑鼠,龙抓到一只白鼠,龙赢了。概率为ji+j×ii+j−1\frac{j}{i+j}\times \frac{i}{i + j - 1}i+jj​×i+j−1i​;
  • 公主抓到一只黑鼠,龙抓到一只黑鼠,跑出来一只黑鼠,转移到 f[i][j−3]f[i][j-3]f[i][j−3]。概率为ji+j×j−1i+j−1×j−2i+j−2\frac {j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{j-2}{i+j-2}i+jj​×i+j−1j−1​×i+j−2j−2​ ;
  • 公主抓到一只黑鼠,龙抓到一只黑鼠,跑出来一只白鼠,转移到 f[i−1][j−2]f[i-1][j-2]f[i−1][j−2]。概率为ji+j×j−1i+j−1×i−1i+j−2\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times\frac{i-1}{i+j-2}i+jj​×i+j−1j−1​×i+j−2i−1​ ;

一定只有这四种情况!

考虑公主赢的概率,第二种情况不参与计算。并且要保证后两种情况合法,所以还要判断i,ji,ji,j 的大小,满足第三种情况至少要有 333 只黑鼠,满足第四种情况要有 111 只白鼠和 222 只黑鼠。

然后是简简单单的代码

#include 
#define endl '\n'
#define int long longusing namespace std;const int N = 1010;double f[N][N];//轮到公主,有i个白鼠j个黑鼠,公主赢的概率
int a, b;void solve()
{cin >> a >> b;for (int i = 0; i <= a; i++) f[i][0] = 1;for (int i = 0; i <= b; i++) f[0][i] = 0;for (int i = 1; i <= a; i++)for (int j = 1; j <= b; j++){f[i][j] += 1.0 * i / (i + j);if (j > 2) f[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * f[i][j - 3];if (i > 0 && j > 1) f[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * f[i - 1][j - 2];}printf("%.9f", f[a][b]);
}
signed main(){// ios_base::sync_with_stdio(false), cin.tie(0);int T = 1;// cin >> T;while(T--) solve();return 0;
}

2. Jon and Orbs

转移方程好好推捏,但代码实现(对憨憨)很不友好!

还是分类讨论:

令f[i][j]f[i][j]f[i][j]第iii天产生了jjj种球的概率,他能转移到两种情况:第j+1j+1j+1天产生的是和以前相同种类的球,概率是ik\frac{i}{k}ki​,转移到状态f[i][j+1]f[i][j+1]f[i][j+1]和第j+1j+1j+1天产生了一种新的类型的球,概率为k−ik\frac{k-i}{k}kk−i​,转移到状态f[i+1][j+1]f[i+1][j+1]f[i+1][j+1].

那么我们可以得到转移方程为:

f[i][j] = j / k * f[i][j + 1] + (k - j) / k * f[i + 1][j + 1]

但这是逆推,末状态我们是不知道的,我们只能知道初状态

f[0][0] = 1 && f[i][0] = 0(i != 0)

所以我们将思维逆转一下:

令f[i][j]f[i][j]f[i][j]第iii天产生了jjj种球的概率,他能从两种情况转移而来:第jjj天产生的是和以前相同种类的球,概率是ik\frac{i}{k}ki​,从状态f[i][j−1]f[i][j-1]f[i][j−1]转移过来和第jjj天产生了一种新的类型的球,概率为k−(i−1)k\frac{k-(i-1)}{k}kk−(i−1)​,从状态f[i−1][j−1]f[i-1][j-1]f[i−1][j−1]转移过来.

那么我们可以得到转移方程为:

f[i][j] = j / k * f[i - 1][j] + (k - j + 1) / k * f[i - 1][j - 1]
//我们可以发现,下一维的i用的是上一维的i的数据,那么我们可以借助滚动数组采取逆序枚举来实现对第一维的优化
//注意f[i][0] = (i == 0 ? 0 : 1);

根据已知的初状态我们就可以求解了

#include 
#define endl '\n'
// #define int long longusing namespace std;const int N = 1010;// double f[N][N];
double f[N];//第一维用滚动数组实现
int day[N];void solve()
{int k, q;cin >> k >> q;// f[0][0] =1;f[0] = 1;//当i==0时,f[i][0] = 1, 否则f[i][0] = 0int p = 1;for (int i = 1; p <= 1000; i++){for (int j = k; j >= 1; j--){// f[j] = (j * f[j] + (k - j + 1) * f[j - 1]) / k; //√f[j] = 1.0 * j / k * f[j] + 1.0 * (k - j + 1) / k * f[j - 1];//注意i,j都是整数,运算得不到想要的浮点数,所以别忘了精度转换!!!!!!!}while (f[k] * 2000 >= p + 1e-7) day[p] = i, p++;//只要第i天后的概率满足该pi,就一直记录答案直到不满足,继续循环下一天f[0] = 0;//之后用到的都是i>0的一层的结果,所以要改成0}    while(q--)//因为有多次询问,我们将所有的pi对应哪一天都预处理出来存在数组中{int x; cin >> x;printf("%d\n", day[x]);}
}
signed main(){// ios_base::sync_with_stdio(false), cin.tie(0);int T = 1;// cin >> T;while(T--) solve();return 0;
}

期望DP

1. Collecting Bugs

令f[i][j]f[i][j]f[i][j] 为已经找到iii 种 bug 分类,jjj 个子系统的 bug,达到目标状态的期望天数。这里的目标状态是找到nnn 种 bug 分类,sss 个子系统的 bug。那么就有f[n][s]=0f[n][s]=0f[n][s]=0 ,因为已经达到了目标状态,不需要用更多的天数去发现 bug 了,于是就以目标状态为起点开始递推,答案是f[0][0]f[0][0]f[0][0]。

考虑 的状态转移:

  • f[i][j]f[i][j]f[i][j]发现一个 bug 属于已经发现的iii 种 bug 分类,jjj 个子系统,概率为p1=in×jsp_1=\frac{i}{n}\times \frac{j}{s}p1​=ni​×sj​
  • f[i][j+1]f[i][j+1]f[i][j+1],发现一个 bug 属于已经发现的iii 种 bug 分类,不属于已经发现的子系统,概率为 p1=in×s−jsp_1=\frac{i}{n}\times \frac{s-j}{s}p1​=ni​×ss−j​
  • f[i+1][j]f[i+1][j]f[i+1][j],发现一个 bug 不属于已经发现 bug 分类,属于jjj 个子系统,概率为 p1=n−in×jsp_1=\frac{n-i}{n}\times \frac{j}{s}p1​=nn−i​×sj​
  • f[i+1][j+1]f[i+1][j+1]f[i+1][j+1],发现一个 bug 不属于已经发现 bug 分类,不属于已经发现的子系统,概率为 p1=n−in×s−jsp_1=\frac{n-i}{n}\times \frac{s-j}{s}p1​=nn−i​×ss−j​

再根据期望的线性性质,就可以得到状态转移方程:

f[i][j] = p1 * f[i][j] + p2 * f[i][j + 1] + p3 * f[i + 1][j] + p4 * f[i + 1][j + 1]
//一定要化简后才能用来转移,因为我们要得到f[i][j]状态,只有等式左边才能有f[i][j],右边不能有!!!
//化简后
f[i][j] = ((j - s) * (i - n) * f[i + 1][j + 1] + j * (n - 2) * f[i + 1][j] + i * (s - j) * f[i][j + 1] + n * s) / (n * s - i * j)

简单的代码:

// #include 
#include 
#define endl '\n'
// #define int long longusing namespace std;const int N = 1010;int n, s;
double f[N][N];void solve()
{cin >> n >> s;f[n][s] = 0;for (int i = n; i >= 0; i--)for (int j = s; j >= 0; j--){if (i == n && j == s) continue;// f[i][j] =  f[i][j] * i / n * j / s  // + f[i + 1][j] * (n - i) / n * j / s // + f[i][j + 1] * i / n * (s - j) / s  // + f[i + 1][j + 1] * (n - i) / n * (s - j) / s  // + 1;//未化简,不能用来状态转移哦f[i][j] = (f[i + 1][j + 1] * (j - s) * (i - n) + f[i + 1][j] * j * (n - i) + f[i][j + 1] * i * (s - j) + n * s) / (n * s - i * j);}printf("%.4f", f[0][0]);
}
signed main(){// ios_base::sync_with_stdio(false), cin.tie(0);int T = 1;// cin >> T;while(T--) solve();return 0;
}

未完待续(希望如此。。。

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...