站队
题目描述
有一条很长的队伍，队伍里面一共有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);
}
