GYM - 101147 K.Touristic Trip

题意：

　　一个人从城市0开始旅行。一共有N座城市，他每到一座城市都会寄一张明信片。给出从一座城市到另一座城市的概率和在每座城市寄出每张明信片的概率。给出长度为k的寄明信片的序列。问在该序列的条件下在第Z个城市寄出第Q张明信片的序列。

题解：

　　条件概率：P(A|B) = P(A,B)/P(B)

　　dp[i][j]代表第i个城市是城市j且寄出第a[i]张明信片的概率。

　　dp[i][j] += sum{dp[i-1][k]*p[k][j]*c[j][a[i]}(0<=j<n)

　　P(B) = sum{dp[k-1][j]}(0,=j<n)

　　令dpp[Q][Z] = dp[Q][Z]　dpp[Q][j] = 0(j!=Z)

　　后面dpp像dp一样算。

　　P(A,B) =sum{dpP[k-1][j]}(0,=j<n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t; 
int n, m, k, q, z;
double p[25][25], c[25][15];
double dp[20][25], dpp[20][25];
int a[20];
int main() {
    freopen("trip.in","r",stdin);
    scanf("%d", &t);
    while(t--) {
        memset(dp, 0, sizeof(dp));
        memset(dpp, 0, sizeof(dpp));
        scanf("%d%d%d%d%d", &n, &m, &k, &q, &z);
        for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) scanf("%lf", &p[i][j]);
        for(int i = 0; i < n; i++) 
        for(int j = 0; j < m; j++) scanf("%lf", &c[i][j]);
        for(int i = 0; i < k; i++) scanf("%d", &a[i]);
        dp[0][0] = c[0][a[0]]; 
        for(int i = 1; i <= q; i++) {
            for(int j = 0; j < n; j++) 
            for(int k = 0; k < n; k++)
            dp[i][j] += dp[i-1][k]*p[k][j]*c[j][a[i]];
        }
        dpp[q][z] = dp[q][z];
        for(int i = q+1; i < k; i++) {
            for(int j = 0; j < n; j++) 
            for(int k = 0; k < n; k++) {
                dp[i][j] += dp[i-1][k]*p[k][j]*c[j][a[i]];
                dpp[i][j] += dpp[i-1][k]*p[k][j]*c[j][a[i]];
            }
        }
        for(int i = 1; i < n; i++) {
            dp[k-1][i] += dp[k-1][i-1];
            dpp[k-1][i] += dpp[k-1][i-1];
        }
        printf("%.3lf\n", dpp[k-1][n-1]/dp[k-1][n-1]);
    }
}

View Code

优质内容筛选与推荐>>
1、IOS开发（63）之GCD执行延迟操作
2、linq语法1
3、HDU 6211 卡常数取模预处理数论
4、入门练习
5、在百度的日子·那些事：开会时的电话声(8)

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看