Skip to content

14164: 【原4164】小源吃苹果

题目

题目描述

author: fur 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4164

吃苹果

题目描述

小源有\(n\)个苹果,他每天都会吃掉一些苹果。
但是小源是个没有主见的人,他每天到底要吃多少个苹果取决于当天剩下多少个。当这一天剩下\(k\)个苹果时,他等概率(即\(\frac{1}{k}\)吃掉\(1,2,\cdots,k\)个苹果。
现在想要知道,小源吃掉\(m\)个苹果期望下需要多少天。

输入格式

一行两个整数\(n,m\),表示最初苹果数和目标苹果数。

输出格式

一个数表示期望天数,保留到小数点后两位。

样例输入

3 3

样例输出

1.83

数据规模

对于30%的数据有
\(m\leq3\)
对于50%的数据有
\(n\leq10\)
对于20%的数据有
\(n=m\)
对于100%的数据有
\(1\leq m\leq n\leq20\)

WashSwang's solution

#include <iostream>
#include <iomanip>
using namespace std;
int m,n;
double dp[1001][1001],ans=0;
int main() {
    cin>>n>>m;
    dp[0][n]=1;
    for (int i=1;i<=n;++i)
        for (int j=0;j<n;++j) {
            for (int k = max(j + 1, n - m + 1); k <= n; ++k)
                dp[i][j] += dp[i - 1][k] / k;
            if (j<=n-m) ans+=i*dp[i][j];
        }
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans;
    return 0;
}