站队

题目描述

有一条很长的队伍，队伍里面一共有n个人。所有的人分为三类：警察，小偷和普通人。将队伍里面的人从前到后由1到n编号，编号为i的人与编号为j的人的距离为i与j之差的绝对值。
每一个警察有一个能力值x，表示他能够监视与他距离不超过x的所有人，小偷被警察发现当且仅当他被一个或多个警察监视到。你知道在整条队伍中，一共有多少个小偷会被警察发现吗？

样例输入
9
X1X#2X#XX
样例输出
3

站队题目地址

Trick可能就只是在标记被抓的贼的时候, 直接在原先char数组上赋值成一个'c', 后面再扫描一遍数组, 统计'c'的个数.

我的代码

public class PoliceCatch {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        String str = input.next();
        char[] A = str.toCharArray();

        for (int i=0; i<A.length; i++) {
            if (A[i]!='X' && A[i]!='#' && A[i]!='c') {
                int r = Integer.parseInt(A[i]+"");
                for (int j=1;j<=r;j++) {
                    if (i-j>=0 && A[i-j]=='X') {
                        A[i-j] = 'c';  //mark Caught thieves
                    }
                    if (i+j<=n-1 && A[i+j]=='X') {
                        A[i+j] = 'c';  //mark Caught thieves
                    }
                }
            }
        }
        int count = 0;  //count of caught thieves
        for (int i=0; i<n; i++) {
            if (A[i] == 'c') {
                count++;
            }
        }
        System.out.println(count);
    }

通过考试

题目描述

小明同学要参加一场考试，考试一共有n道题目，小明必须做对至少60%的题目才能通过考试。考试结束后，小明估算出每题做对的概率，p1,p2,...,pn。你能帮他算出他通过考试的概率吗？

样例输入
4
50 50 50 50
样例输出
0.3125

通过考试题目地址

这题我一开始没做出来, 组合数学和古典概率不熟练, 而且想得复杂了,
实际上就是DP, 都是套路....

我的代码

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        double[] P = new double[n+1];
        for (int i=1; i<=n; i++) {  //下标从1~n, 方便计算
            P[i] = input.nextInt()/100.0;  //input 50, get 0.50 as probability
        }  //input over
        int k = (int)Math.ceil(n*0.6);  //至少要答对60%的题目
        double[][] L = new double[n+1][n+1];  //Likelihood array; every element is 0 by default
        L[0][0] = 1;      //L[i][j] Pr(前i题, 正确了j题)的概率大小
        for (int i=1; i<n+1; i++) {  //deal with L[i][0], 初始化
            L[i][0] = (1-P[i])*L[i-1][0];
        }
        for (int i=1; i<n+1; i++) {
            for (int j=1; j<n+1; j++) {
                L[i][j] = P[i]*L[i-1][j-1] + (1-P[i])*L[i-1][j];  //DP状态转换方程
            }
        }
        double chance = 0;
        for (int i=k; i<=n; i++) {  //aggregate L[n][k], L[n][k+1] ... L[n][n],
            chance += L[n][i];  //Pr[通过] = 至少要答对百分60题目的各种可能性的和
        }
        System.out.println(chance);
    }