CodeForces 476B Dreamoon and WiFi 数学 概率 DP

http://codeforces.com/problemset/problem/476/B //数学解法:统计两个串中各字符的个数,判断各需要添加几个. //因为只有两种(+和-),所以只要判断一种(我判断的是+)就可以确定答案了. //Ans=C(c,a)/pow(2,c) #include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<climits> #include<map> #include<bitset> using namespace std; int main() { cout<<fixed<<setprecision(12); cin.sync_with_stdio(false); char str1[15],str2[15]; cin>>str1>>str2; int len=strlen(str1); int pos1=0,pos2=0,a=0,b=0,c=0; for (int i=0; i<len; i++) { if (str1[i]=='+') pos1++; else pos2++; if (str2[i]=='+') a++; else if (str2[i]=='-') b++; else c++; } double Ans; if (a==pos1&&b==pos2) Ans=1; else if (c==0||a+c<pos1||b+c<pos2) Ans=0; else { double temp; a=pos1-a; b=pos2-b; if (a==0||b==0) temp=1; else { double c1=1,c2=1; for (int i=c; i>c-a; i--) c1=c1*i; for (int i=1; i<=a; i++) c2=c2*i; temp=c1/c2; } Ans=temp/pow(2,c); } cout<<Ans; return 0; } //DP解法 //F[i][j]表示走到第i个问号,坐标为j时的概率.因为坐标可能为负,所以数组前移10距离. //F[i][j]=F[i-1][j-1]*0.5+F[i-1][j+1]*0.5 #include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<climits> #include<map> #include<bitset> using namespace std; int main() { double F[50][50]= {0}; cout<<fixed<<setprecision(12); cin.sync_with_stdio(false); char str1[15],str2[15]; cin>>str1>>str2; int len=strlen(str1); int pos1=0,pos2=0,pos3=0; for (int i=0; i<len; i++) { if (str1[i]=='+') pos1++; else pos1--; if (str2[i]=='+') pos2++; else if (str2[i]=='-') pos2--; else pos3++; } F[0+10][pos2+10]=1; for (int i=1; i<=pos3; i++) for (int j=-10; j<=len; j++) F[i+10][j+10]=F[i-1+10][j-1+10]*0.5+F[i-1+10][j+1+10]*0.5; cout<<F[pos3+10][pos1+10]; return 0; }