UVA10218 - Let's Dance !!!

keywords: 搜索

网上的题解很少，写一份

dp(递归)

/*
  Idea:
    - Dynamic Programming.
    - dp[men][rem]:
      `men` represents the number of the gentle men take candies till now.
      `rem` represents the number of remaining candies.
    - In each step calculate the probability of give the current candy
      to a gentle men or to a woman and sum the probabilities.
*/

#include <bits/stdc++.h>

using namespace std;

int m, w, c;
double dp[1010][100]; 

double rec(int mem, int rem)
{
    if (rem == 0){
        return mem % 2 == 0;
    }

    double &ret = dp[mem][rem];
    if (ret != -1) return ret;

    ret = 1.0*m/(m+w) * rec(mem+1, rem-1) + 1.0*w/(m+w) * rec(mem, rem-1);
    return ret;
}

int main()
{
    while (cin >> m >> w >> c){
        if (!m && !w) break;

        for (int i = 0; i <= c; i++)
            for (int j = 0; j <= c; j++) dp[i][j] = -1;

        printf("%0.7lf\n", rec(0, c));
    }

    return 0;
}

dp(循环)

#include <bits/stdc++.h>

using namespace std;

int m, w, c;
double dp[1010][100]; 

int main()
{
    while (cin >> m >> w >> c){
        if (!m && !w) break;

        for (int i = 0; i <= c; i++)
            for (int j = 0; j <= c; j++) dp[i][j] = -1;

        double p = 1.0 * m  / (m + w);
        dp[0][0] = 1.0, dp[0][1] = 0.0;  //[0]分到偶数，[1]分到奇数

        for (int i = 1; i <= c; i++){
            dp[i][0] = dp[i-1][0] * (1-p) + dp[i-1][1] * p;
            dp[i][1] = dp[i-1][1] * (1-p) + dp[i-1][0] * p;
        }

        printf("%0.7lf\n", dp[c][0]);
    }

    return 0;
}

组合数学

#include <bits/stdc++.h>

using namespace std;

typedef long double ll;

int m, w, c;
ll C[110][110];

void init()
{
    for (int i = 0; i <= 100; i++) C[i][0] = 1;
    for (int i = 0; i <= 100; i++) C[i][i] = 1;

    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
}

int main()
{
    init();

    while (cin >> m >> w >> c){
        if (!m && !w) break;

        double p = 1.0 * m / (m + w);
        double ret = 0.0;
        for (int i = 0; i <= c; i += 2){
            ret += C[c][i] * pow(p, i) * pow(1-p, c-i);
        }

        printf("%.7lf\n", ret);
    }

    return 0;
}

愿神与你同在！