程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 3853 LOOPS（概率DP）

HDU 3853 LOOPS（概率DP）

編輯：C++入門知識

HDU 3853 LOOPS（概率DP）

題意：求從(1, 1)點走到(n, m)點的花費能量的期望，每次決策消耗2點能量。每次可以原地不動或者向右或者向下，分別有個概率。

思路：運用全概率期望公式， d[i][j] = a[1]*d[i][j] + a[2]*d[i+1][j] + a[3]*d[i][j+1] + 2，其中a[i]是三個可能情況的概率。因為dp方程要滿足無後效性，所以移項得d[i][j] = (2 + a[2]*d[i+1][j] + a[3]*d[i][j+1]) / (1 - a[i][j])。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 1000 + 10;
int T,n,m,vis[maxn][maxn],kase = 0;
double d[maxn][maxn];
struct node {
    double a, b, c;
}a[maxn][maxn];
double dp(int r, int c) {
    double& ans = d[r][c];
    if(r == n && c == m) return 0;
    if(vis[r][c] == kase) return ans;
    vis[r][c] = kase;
    if(fabs(a[r][c].a - 1) < eps) return 0;
    ans = 0.0;
    if(r < n) ans += dp(r+1, c) * a[r][c].c;
    if(c < m) ans += dp(r, c+1) * a[r][c].b;
    ans += 2;
    ans /= (1 - a[r][c].a);
    return ans;
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                scanf("%lf%lf%lf",&a[i][j].a,&a[i][j].b,&a[i][j].c);
            }
        }
        ++kase;
        double ans = dp(1, 1);
        printf("%.3f\n",ans);
    }
    return 0;
}