2023牛客寒假算法基础集训营1-M（DP）

https://ac.nowcoder.com/acm/contest/46800/M 题目关键在于构建方程：

• \(dp[i][j] = \max_{k \leq j} (dp[i-1][j-k] + \frac{k}{m-(j-k)})\)

i 是已经分了 i 个人， j 是已经分发了j个仙贝

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long

int n,m;
double dp[510][510];

int main(){
    cin>>n>>m;
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=j;k++){
                if((m-(j-k))>0)
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k]+(double)k/(m-(j-k)));
            }
        }
    }
    printf("%.10lf\n",dp[n][m]);
    return 0;
}