站隊
題目描述
有一條很長的隊伍，隊伍里面一共有n個人九火。所有的人分為三類：警察赚窃，小偷和普通人。將隊伍里面的人從前到后由1到n編號岔激，編號為i的人與編號為j的人的距離為i與j之差的絕對值勒极。
每一個警察有一個能力值x，表示他能夠監(jiān)視與他距離不超過x的所有人虑鼎，小偷被警察發(fā)現(xiàn)當(dāng)且僅當(dāng)他被一個或多個警察監(jiān)視到辱匿。你知道在整條隊伍中键痛，一共有多少個小偷會被警察發(fā)現(xiàn)嗎？
樣例輸入
9
X1X#2X#XX
樣例輸出
3
Trick可能就只是在標(biāo)記被抓的賊的時候, 直接在原先char數(shù)組上賦值成一個'c', 后面再掃描一遍數(shù)組, 統(tǒng)計'c'的個數(shù).
我的代碼
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);
}
通過考試
題目描述
小明同學(xué)要參加一場考試匾七，考試一共有n道題目絮短，小明必須做對至少60%的題目才能通過考試∽蛞洌考試結(jié)束后丁频，小明估算出每題做對的概率，p1,p2,...,pn邑贴。你能幫他算出他通過考試的概率嗎席里？
樣例輸入
4
50 50 50 50
樣例輸出
0.3125
這題我一開始沒做出來, 組合數(shù)學(xué)和古典概率不熟練, 而且想得復(fù)雜了,
實際上就是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++) { //下標(biāo)從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狀態(tài)轉(zhuǎn)換方程
}
}
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);
}
