| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
简单DP一遍过,大水题咋木人做#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ii++){
int pa, pb, K, L;
scanf("%d%d%d%d", &pa, &pb, &K, &L);
double Pa = pa/100.0, Pb = pb/100.0;
double dpa[102][102][2], dpb[102][102][2];
dpa[0][0][0] = 1, dpa[0][0][1] = 0, dpb[0][0][0] = 0, dpb[0][0][1] = 1;
for(int s = 0; s <= L; s++){
for(int t = 0; t < L; t++){
if(s == 0 && t == 0) continue;
dpa[s][t][0] = 0;
if(s != 0) dpa[s][t][0] += (dpa[s-1][t][0]*Pa + dpa[s-1][t][1]*(1-Pb));
if(s < L){
dpa[s][t][1] = 0;
if(t != 0) dpa[s][t][1] += (dpa[s][t-1][0]*(1-Pa) + dpa[s][t-1][1]*Pb);
}
}
}
for(int s = 0; s <= L; s++){
for(int t = 0; t < L; t++){
if(s == 0 && t == 0) continue;
dpb[s][t][0] = 0;
if(s != 0) dpb[s][t][0] += (dpb[s-1][t][0]*Pa + dpb[s-1][t][1]*(1-Pb));
if(s < L){
dpb[s][t][1] = 0;
if(t != 0) dpb[s][t][1] += (dpb[s][t-1][0]*(1-Pa) + dpb[s][t-1][1]*Pb);
}
}
}
double PA = 0, PB = 0;
for(int j = 0; j < L; j++) PA += dpa[L][j][0];
for(int j = 0; j < L; j++) PB += dpb[L][j][0];
double P[2];
P[0] = PA, P[1] = PB;
double DPA[200][200], DPB[200][200];
DPA[0][0] = 0.5, DPB[0][0] = 0.5;
for(int La = 0; La < K; La++){
for(int Lb = 0; Lb < K; Lb++){
if(La == 0 && Lb == 0) continue;
double PX = P[(La+Lb+1)%2];
DPA[La][Lb] = 0;
if(La>0) DPA[La][Lb] += DPA[La-1][Lb]*PX;
if(Lb>0) DPA[La][Lb] += DPA[La][Lb-1]*(1-PX);
}
}
for(int Lb = 0; Lb < K; Lb++){
double PX = P[(K+Lb+1)%2];
DPA[K][Lb] = DPA[K-1][Lb]*PX;
}
for(int La = 0; La < K; La++){
for(int Lb = 0; Lb < K; Lb++){
if(La == 0 && Lb == 0) continue;
double PX = P[(La+Lb)%2];
DPB[La][Lb] = 0;
if(La>0) DPB[La][Lb] += DPB[La-1][Lb]*PX;
if(Lb>0) DPB[La][Lb] += DPB[La][Lb-1]*(1-PX);
}
}
for(int Lb = 0; Lb < K; Lb++){
double PX = P[(K+Lb)%2];
DPB[K][Lb] = DPB[K-1][Lb]*PX;
}
double ans = 0;
for(int j = 0; j < K; j++) ans += DPA[K][j];
for(int j = 0; j < K; j++) ans += DPB[K][j];
ans *= 100;
printf("%.1lf\n", ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator