Topcoder SRM 651 div1 250 題解 （機率dp）

題意：給一個有n個整數的數組d。第一次随機選擇一個數，以後每次随機選擇一個沒選過的數，如果這個數的下标大于前一個數，則不要這個數并停止選擇。否則，繼續選數，除非所有的數都選擇就停止選擇。問最後選出來的數的和的期望值。n<=250.

題解：這題有多種做法。

方法一：用dp[i][j] 表示下标為i到n的數選了j個，第i個數必選的期望值。我們轉移的時候，需要記錄每個狀态的機率值。是以我們用f[i][j] 表示目前狀态下的機率值。最後計算答案的時候在計算終止的機率。詳情見代碼：

#line 4 "RandomPancakeStack.cpp"
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <sstream>
#define OUT(x) cout << #x << ": " << (x) << endl
#define SZ(x) ((int)x.size())
#define FOR(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long LL;
double dp[310][310],p[310][310];
class RandomPancakeStack
{
public:
    double expectedDeliciousness(vector <int> d)
    {
        int n=d.size();
        int i,j,k;
        for(i=0;i<n;i++)
        {
            dp[1][i]=d[i]*1.0/n;
            p[1][i]=1.0/n;
        }
        for(i=2;i<=n;i++)
        {
            for(j=0;j<=n-i;j++)
            {
                dp[i][j]=0;
                p[i][j]=0;
                for(k=j+1;k<=n-i+1;k++)
                {
                    dp[i][j]+=dp[i-1][k]/(n-i+1)+d[j]*p[i-1][k]/(n-i+1);
                    p[i][j]+=p[i-1][k]/(n-i+1);
                }
            }
        }
        double re=0;
        for(i=1;i<=n;i++)
        {
            for(j=0;j<=n-i;j++)
            {
                if(i==n)
                {
                    re+=dp[i][j];
                }
                else
                {
                    re+=dp[i][j]*(n-j-i)/(n-i);
                }
            }
        }
        return re;
    }


};


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
           

方法二：分别計算每個數的期望值，而計算這個數的期望值需要計算所有選擇到這個數的機率。是以我們用dp[i][j]表示i+1到n已經選了j個數，然後選到第i個數的機率。最後再統計答案：

#line 4 "RandomPancakeStack.cpp"
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <sstream>
#define OUT(x) cout << #x << ": " << (x) << endl
#define SZ(x) ((int)x.size())
#define FOR(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long LL;
double dp[310][310];
class RandomPancakeStack
{
public:
    double expectedDeliciousness(vector <int> d)
    {
        int i,j,k;
        int n=d.size();
        for(i=0;i<n;i++)
        {
            dp[0][i]=1.0/n;
        }
        for(i=1;i<n;i++)
        {
            for(j=0;j<n-i;j++)
            {
                for(k=j+1;k<=n-i;k++)
                {
                    dp[i][j]+=dp[i-1][k]/(n-i);
                }
            }
        }
        double re=0;
        for(i=0;i<=n-1;i++)
        {
            for(j=0;j<n-i;j++)
            {
                re+=d[j]*dp[i][j];
            }
        }
        return re;
    }


};


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
           

方法三：用dp[i][j]表示目前可以從i-1到0中選，共有j個數沒被選的期望值。那麼最後答案就是dp[n][n]。

那麼轉移就是：

dp[i][j]+=(d[k]+dp[k][j-1])/j 。0<=k<i

代碼如下：

#line 4 "RandomPancakeStack.cpp"
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <sstream>
#define OUT(x) cout << #x << ": " << (x) << endl
#define SZ(x) ((int)x.size())
#define FOR(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long LL;
double dp[310][310];
class RandomPancakeStack
{
public:
    double expectedDeliciousness(vector <int> d)
    {
        int i,j,k;
        int n=d.size();
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                for(k=0;k<i;k++)
                {
                    dp[i][j]+=(d[k]+dp[k][j-1])/j;
                }
            }
        }
        return dp[n][n];
    }


};


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor
           

總結：對于求解期望類問題一般是用dp[i]表示從狀态目前i走到結束狀态的期望值，按照事件發生的先後順序就行轉移，轉移一般是：

dp[i]+=(val[i]+dp[k])*p;  (val[i]表示該事件的消費或價值，p表示發生目前事件的機率)