补题 [2023牛客寒假算法基础集训营1] 本题主要考察了找规律

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

小波奇由于冲动消费，不小心买多了章鱼仙贝，买了一共 $ m$ 份章鱼仙贝，于是她只能把这些仙贝分给 $n$ 位朋友。

img

小波奇日常想太多，她认为分仙贝时好感度的变化是有规律的，不过并不是给的仙贝越多，好感度上升的就越多，而是应该看小波奇给出的仙贝数与她当前手里总仙贝的比值。也就是说，若小波奇当前还剩下 $x(x>0)$ 个仙贝，并给了一位朋友 $y$ 个仙贝（ $x,y$ 都为整数），则这位朋友对小波奇的好感度将增加 $y/x$（这个值可以为小数）。

现在，小波奇可以任意安排送仙贝的顺序和每次送仙贝的个数，但不能给同一个人送两次仙贝，允许最后手中还有剩余的仙贝，允许最终有朋友没有分到仙贝。社恐的朋友非常重要，所以请你帮助小波奇算一算，在最优送仙贝策略下，小波奇和所有人的好感度之和最大为多少（假设初始小波奇和所有人好感度都为 $0$ ）。

输入描述

输入包括两个整数 $n,m(1 \leq n,m \leq 500)$ ，表示小波奇的朋友数和仙贝数。

输出描述

输出问题的答案，即小波奇与朋友们的好感度之和的最大值，考虑到可能存在的浮点误差，你的答案与标准答案的相对误差若在 $10^{-6}$ 之内，就将被判为正确。

输入

1
3 3

输出

1
1.833333333

说明

1
对应的分配方案是：小波奇初始有3个仙贝，给第一个朋友1块，收获了1/3的好感度；现在小波奇有2个仙贝，给第二个朋友1块，收获了1/2的好感度；最后，小波奇把最后一块仙贝给了第三个朋友，收获了1/1的好感度。因此，总好感度为11/6，并且可以看出没有更好的分配方案。

题解

题目解析

诈骗题, 事实上并没有规律… 这是一道dp题,有点类似于背包, 但是并不是背包.

简单写一下思考流程吧, 看出来是用dp了之后, 我们依照想法就开始对状态进行考虑了. 我们定义dp数组: dp[i][j]=已经分给了i个个人,送出了j个物品收获的最大值 .

接下来就是怎么转移了, $i$ 好考虑, 一定是从 $i-1$ 转移到 $i$ . 接下来就是第二维, 我们可以得到以下式子:

这里用背包解释好理解, 我们把所有可以组成 $j$ 个物品的方式都遍历一遍, 从这些方式中我们就可以找到其最大值. 因为前面dp保存下来的都是最大的嘛, 我们就可以利用dp数组来转移.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(500);

double dp[MAXN][MAXN];

signed main(){
	int n,m;
	cin >> n >> m;
	mem(dp,-0x3f3f3f3f);
	dp[0][0] = 0;
	fa(i,1,n){
		fa(j,0,m){
			fb(k,j,0){
				dp[i][j] = max(dp[i][j],dp[i-1][j-k]+(double)k/(m-(j-k)));
			}
		}
	}
	cout << printf("%.9f",dp[n][m]) << endl;
	return 0;
}