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("%.10lf\n", dpf(n - k, k));

}