Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

简单DP一遍过,大水题咋木人做

Posted by KatrineYang at 2016-09-10 23:53:21 on Problem 1280 and last updated at 2016-09-10 23:54:05
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator