等機率事件最優政策問題

仍然是從考試題說起

​​noip模拟74​​第\(3\)題

這個題的第一個結論，兩人政策相同

而第一個人的最優政策并不能直接由目前的值推出來，而是需要從後面赢的機率得到目前政策

我們隻需要對應的轉移一下就行了，具體可以看那篇考試的題解

​​多校沖刺 noip 11.01​​第\(2\)題

和上面那個是一樣的，隻不過這個變成了期望

最優政策仍然是由後面的期望決定的

目前這一次的期望一定是可以選的範圍的中點

可以直接倒推轉移

一點總結

遇到這樣的最優政策的題

可以先瞪眼，瞪出一些沒有用的政策(當然這并沒有什麼用)

然後就可以開始倒推轉移了，所有最優政策全是根據後面的機率或者期望得到的

所謂最優政策，不過是他也會像我們一樣推出來整個遊戲的機率然後選擇了機率或者期望最大的那種操作

并不是像賭博一樣我去賭某一種政策的勝率

而是在平均情況下最優的決策

就像是海盜分金，我們從後往前推的話，發現第一個人有這麼大的權利啊

例題

​​HDU 5781 ATM Mechine​​

這個題仍然是看上去一點思路都沒有

是以我就去看題解了，看完題解好像了解了一點點

首先我們仍然不知道最優政策是啥，可能你會覺得最優政策就是二分着取錢

二分的最劣情況不過是，取出來錢的次數+被警告的次數\(=log\)

沒準賭一把取錢的次數更少呢？？

如果警告次數上限小于\(log\)呢？隻能是\(DP\)

是以我們繼續剛才的思路：倒推！！！

枚舉目前決策，從後面的狀态轉移

如果目前決策确定了，那麼被警告和取出錢的機率也就确定了，也就是說轉移系數确定了

\(dp_{i,j}\)表示目前錢數上限是\(i\)，最多被警告\(j\)次的期望取錢次數

注意這裡的\(j\)最大是\(log\)，原因就是上面的二分思想

如果上限很大的話，我二分着取的次數可能是非常優秀的政策

簡單來說，二分取錢在這個題裡面是最劣的決策，因為他太保守！！！

AC_code​

​

#include<bits/stdc++.h>
using namespace std;
#define fxt(i,x,y) for(int i=(x);i<=(y);i++)
#define pyt(i,x,y) for(int i=(x);i>=(y);i--)
const int N=2e3+5;
const int M=15;
int n,w;
double f[N][M];
signed main(){
    fxt(i,0,2000)fxt(j,0,12)f[i][j]=1e9;
    fxt(i,0,12)f[0][i]=0;
    fxt(i,1,2000)fxt(j,1,12)fxt(k,1,i){
        f[i][j]=min(f[i][j],f[i-k][j]*(i-k+1)/(i+1)+f[k-1][j-1]*k/(double)(i+1)+1);
    }
    while(scanf("%d%d",&n,&w)!=EOF){
        w=min(w,12);printf("%.6lf\n",f[n][w]);
    }
}           

​

​