学步园

三维DP:dp[ i ][ j ][ k ]前i场赢j场剩余空间k的概率

3 1 0
10 20 30
-1 -1 2

0.300000000000

1 1 1
100
123

1.000000000000

/**
 * Created by ckboss on 14-9-11.
 */

import java.util.*;

public class WizardsandHugePrize {

    static final int ZERO = 202, END = 404;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int N = in.nextInt(), L = in.nextInt(), K = in.nextInt();

        int[] rest = new int[N + 2];
        double[] p = new double[N + 2];
        double[][][] dp = new double[N + 2][N + 2][END + 2];

        for (int i = 1; i <= N; i++) {
            p[i] = in.nextDouble();
            p[i] /= 100.;
        }

        for (int i = 1; i <= N; i++) {
            rest[i] = in.nextInt();
        }

        dp[0][0][ZERO + K] = 1.0;

        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < i; j++) {
                for (int k = 0; k <= END; k++) {

                    if (rest[i] != -1) {
                        int x = Math.min(k + rest[i], END);
                        dp[i][j + 1][x] += dp[i - 1][j][k] * p[i];
                    } else if (k > 0) {
                        dp[i][j + 1][k - 1] += dp[i - 1][j][k] * p[i];
                    }

                    dp[i][j][k] += dp[i - 1][j][k] * (1 - p[i]);
                }
            }
        }

        double ans = 0.0;
        for (int i = L; i <= N; i++) {
            for (int j = ZERO; j <= END; j++) {
                ans += dp[N][i][j];
            }
        }

        System.out.println(ans);
    }
}