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