Submission #757712

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
double mem[1005][1005];
int n,k;
int N;

double solve(int n,int k){
  if(k==0)return 0.0;
  if(n==1)return 1.0;
  if(mem[n][k]!=-1)return mem[n][k];
  double np=(double)((n-1)*(N-n))/(double)(n*(N-n+1));
  double p=1.0/(double)n;
  double q=1.0-p-np;
  double res=0.0;
  res=max(res,p+q*solve(n-1,k-1) );
  res=max(res,q* solve(n-1,k) );
  return mem[n][k]= (res + np*solve(n-1,k));
}

int main(){
  for(int i=0;i<1005;i++)
    for(int j=0;j<1005;j++)
      mem[i][j]=-1;
  cin>>n>>k;
  N=n;
  printf("%.8f\n",solve(n,k));
  return 0;
}

Submission Info

Judge Result