链接

题意：有m个仙贝分给n个人，每个人的好感度为（分出的）/（当前剩余的）。求所有人好感度之和最大为多少。

题解：动态规划，dp[i][j]表示前i个人有m个仙贝的情况下最大好感度。一个简单的动态规划问题，再用一个k表示分给当前人的仙贝。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <math.h>
#include <string>
#define PI 3.14159
using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 600;
const int mod = 1e9+7;
double dp[N][N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=j;k++)
            {
                dp[i][j] = max(dp[i][j],dp[i-1][j-k]+1.0 * k / (m-j+k));
            }
        }
    }
    printf("%lf",dp[n][m]);
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int T = 1;
    while(T--)
    {
        solve();
    }
}