ecnu 개인전 B Black Peter dp

10333 단어 dp

제목 링크


https://codeforces.com/gym/102190

문제풀이의 방향.


dp[i][0]dp[i][0]dp[i][0]를 설정하면 거북이가 맞은편에 있고 양쪽에 각각 한 장의 카드가 있다. ii가 먼저 이길 확률을 dp[i][1]dp[i]로 설정한다. [1]dp[i][1]는 거북이가 자신에게 있고 양쪽에 각각 한 장의 카드가 있어 ii가 먼저 이길 확률을 나타낸다.
거북이 는 맞은편 에서 두 가지 이동 방식 이 있는데, 각각 맞은편 거북이 를 뽑는 것 과 맞은편 의 정상 패 를 뽑는 것 이다
내가 먼저 다음 상태로 이동하면 바로 맞은편에서 먼저 가는 것이다. dp방정식은 내가 이길 확률을 나타내고 다음 상태로 이동하면 상대방이 진다.
전이 방정식은 다음과 같다. dp [i] [0] = i + 1\8727(1: d p [i: 1] [1]] [1]] + 1 i + 1\8727(1: d p [i] [0]]) dp[i]]] =\rac {i} {i+1} * (1-dp[i] [1] [1]]]]) + 1 i + [1] [1]]]) + 1 i + 1 i + 1 i + 1 i + 1 i + 1 [1] * * (1-dp[i] [0] [0] [0] [1] [1] [1] [1] [1] [1] [1] [1 i [1] [1] [1] [1] [1] [ii[1] [1] [1] [1] [1dp[i][0]) dp[i] [1] = 1 - d p [i - 1] [0] dp[i] [1] = 1 - dp[i-1] [0] dp[i] [1] = 1 - dp[i - 1] [0]
또한 dp[i][0]dp[i][0]dp[i][0]와 dp[i][1]dp[i][1]dp[i][1]는 수치상 상관없이 정상적으로 이동하면 된다
#include 
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define debug cout<
#define pb  push_back
#define endl '
'
const int mod=(int)1e9+7; const int maxn=(int)1e6+5; string s1,s2; int t,n; //0 ,1 double dp[maxn][2]; void init() { dp[0][0]=1.0,dp[0][1]=0.0; for(int i=1;i<maxn;i++) { dp[i][0]=(1+i*(1-dp[i-1][1]))/(i+2); dp[i][1]=1-dp[i-1][0]; } } signed main() { init(); //cout< IOS cin>>t; while(t--) { cin>>n; cin>>s1>>s2; int num=0; int fl=0; for(int i=0;i<n;i++) { if(s1[i]=='1'&&s2[i]=='1') { num++; } if(s1[i]=='1'&&s2[i]=='0') { fl=1; } } cout<<fixed<<setprecision(10)<<dp[num][fl]<<endl; } return 0; }

좋은 웹페이지 즐겨찾기