URAL 1994 The Emperor's plan 求组合数 大数用log+exp处理

URAL 1994 The Emperor's plan 求组合数 大数用log

#include<functional>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<queue>
#include<map>
#include<set>
#include <stack>
#define REP(i,n) for(int i=0; i<n; i++)
#define PB push_back
#define LL long long
#define CLR(a,b) memset(a,b,sizeof(a))
using namespace std;

const int maxn = 210;

double LOG[210];
void pre()
{
    for (int i = 1; i < 210; i++)
        LOG[i] = LOG[i - 1] + log(i * 1.0);
}
double CN(int a,int b)
{
    return LOG[b] - LOG[a] - LOG[b - a];
}
double PN(int a,int b,int c,int d)
{
    return exp( CN(c,a) + CN(d,b) - CN(c + d,a + b) );
}

double dp[210][21];
bool vis[210][21];

double dpf(int n,int k)
{
    if (k == 0) return n;
    if (n <= k) return 0;
    if (vis[n][k]) return dp[n][k];
    vis[n][k] = 1;
    double &ans = dp[n][k];
    ans = 0;
    n -= k;

    int sum = n + k;
    for (int i = 1; i < sum; i++)
    {
        double now = 0;
        int x = min(i,k);
        for (int j = 0; j <= x; j++)
            now += dpf(n - (i - j),k - j) * PN(n,k,i - j,j);
        ans = max(ans,now);
    }
    return  ans;
}

/***求组合数，无效值为0
const int maxcn = 20;
int cn[maxcn][maxcn];
int init()
{
    for (int i = 1; i < maxcn; i++)
    {
        cn[i][0] = cn[i][i] = 1;
        for (int j = 1; j < i; j++)
            cn[i][j] = cn[i - 1][j - 1] + cn[i - 1][j];
    }
}
*/

int main()
{
    int n,k;
    pre();
    scanf("%d%d",&n,&k);
    printf("%.10lfn",dpf(n - k,k));
}