D小红升装备
思路：
1、n和x都很小，我们考虑用dp。
2、其实有点类似于完全背包问题，装备代表每个物品，金币是体积，战力是价值，最多升到k级，代表每个物品最多选择k次。
3、状态表示：dp[i][j]表示我们从前i个装备里面选，花费的金币不超过j的方案的战力的集合; 属性值：最大值
4、状态转移：
分两类：（1） 不选第i个装备 ： dp[i][j] = dp[i-1][j]
(2) 选第i个装备，选择之后还要分为k+1类，即装备升0--k级
当装备升k级的时候，dp[i][j] = dp[i-1][j - y - k*p] + power;
分析一下，第i个装备选了并且升了k级，花费的金币为 y + k * p , 所以上一个的状态为
dp[i-1][j - y - k * p]----> dp[i][j] = dp[i-1][j - y - k*p] + power(第i个装备升k级获得的战力);
5、注意数据为1e9 很敏感我们用long long , 不然会爆int
#include<bits/stdc++.h>
using namespace std;
const int N = 310;
typedef long long LL;
LL dp[N][N];
LL a[N][5];
/*
3 10
10 3 5 2 100
100 20 5 4 100
20 2 1 10 1
*/
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3] >> a[i][4];
}
for(int i = 1; i <= n; i++)
{
//别代表装备初始战力，购买该装备需要的金币、升1级花费的金币、升1级提升的战力、最高可以提升的等级。
LL x, y, z, p, l;
x = a[i][0], y = a[i][1], z = a[i][2], p = a[i][3], l = a[i][4];
for(int j = 0; j <= m; j ++)
{
// 不购买第i个装备
dp[i][j] = dp[i-1][j];
//购买第i个装备
if(j >= y)
{
for(int k = 0; k <= l && j - y - k * z >= 0; k ++)
{
dp[i][j] = max(dp[i][j], dp[i-1][j - y - k * z] + x + (LL)k * p);
}
}
}
}
cout << dp[n][m] <<endl;
return 0;
}
E 矩阵的划分
思路
1、思维题：要直知道一些结论，不然就需要猜测。
2、首先我们想一想怎么样可以让分数最大化，两种摆放的方法，如果说两种的得分不一样，我们肯定优先考虑得分高的方案，并且将它摆满，如果可以摆满这肯定是最优的方案。
3、如果单独的一种不能摆满，我们就要考虑两者混合的情况。
4、我们考虑怎么样可以尽可能的摆满，首先题目保证n是偶数，所以说2 * 2 的摆法一定可以摆满；关键是L型的如何考虑。
5、我们考虑一下L型的摆放情况：
（1）如果n是3 的倍数，全部摆放L ，不可能只剩一个格子，换句话说，就是剩余的格子数大于1。(应为 L型的只能凑出来2、3)
（2）如果n不是3的倍数，全部摆放L，一定有一个方案使得最后恰好只剩一个格子。
6、综合以上的情况，我们可以得出以下结论：
（1）当n是3的倍数，并且加上题目的条件，n是6的倍数，这时候两种方案都可以填满，所以 res = max(n * n /3 * x,n * n / 4 * y )
(2) 当n不是3 的倍数的时候，我们要加上两者混合的情况，因为填2 * 2 的一定可以填满，所以混合的情况就出现在填L剩一个格子的时候，我们可以把这一个L加上空格换成2 * 2 的摆放。此时就会有三种情况了，我们取一个最大值。
- 尽可能摆放L型的：我们知道它最少可以剩一个格子，所以结果的数量是（n * n - 1）/ 3 * x
- 两者混合的时候，就是L尽可能摆满减掉最后替换的格子，（n * n - 1）/ 3 - x + y
- 尽可能摆满2 * 2 的，一定可以摆满（n * n）/ 4 * y
res = max(（n * n - 1）/ 3 * x, （n * n - 1）/ 3 - x + y, （n * n）/ 4 * y)
7、有点别扭的地方，就是说我们在混合的时候为什么不能一半的L和一半的田，其实你想一下，如果两者的价值不一样，我们肯定都摆价值大的最后的结果更大。
但是还应该考虑的问题是L型的摆法摆放的个数肯定会比田字形摆放的多。这点还没想明白！！！
我们可以这样想，在相同的面积之下，不管摆放的个数的多少，我们是求得和的最大值，即 个数 * 每个价值 的最大值，只考虑一个方面是不行的。
F 小红拿宝箱
思路
1、首先大体上分为两大类：（1）抽到的第一个宝箱不拿，直接消耗完不拿的次数，然后拿取的方案就是在所有的宝箱里里面任意选两个，求期望；res = (ai + aj)/C(n,2);
（2）抽到的第一个宝箱我们拿，接下来我们就考虑剩下的n-1个宝箱，再拿一个并且还有一次“不拿的机会”。
2、我们着重考虑一下第二种方案。
3、我们第一次拿了a[i] , 第二次就是从剩下的n-1 个里面再拿一个，假设我们第二次拿的是a[j], 因为我们还有一次不拿的机会，所以我们可以选择拿或不拿：
（1）我们不拿a[j], 那么第二个宝箱的期望就是n-1个宝箱里面任取一个的期望：avge1 = (sum - a[i])/(n-1);
（2）我们拿a[j]，但是我们要看一下a[j]和平均值的大小关系，如果a[j] 小于平均值，我们干脆不拿，a[j]的期望==avge1；如果a[j]的值大于均值我们拿a[j]，因为这样的期望会更大；所以对与每个a[i] : avge_j += max(avge1, a[j])(j:0-n)， avge_j = avge_j / n-1, res_i = avge_j + a[i];
4、当我们求a[j]的期望的时候还要再遍历一边数组，复杂度是O（n * n）的，我们考虑优化一下。avge_j其实就是：大于平均数的和加上不于平均数的数取avge1的和，前者我们可以用后缀和来求，从而优化掉一层for（）循环
5、最后的res 我们求得其实是每种选取方案期望的和，我们还要除以n
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
double a[N], sum[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> a[i];
}
sort(a, a + n);
for(int i = n - 1; i >= 0; i --)
{
sum[i] = sum[i+1] + a[i];//后缀和
}
if(n <= 2)
{
cout << sum[0] << endl;
return 0;
}
//第一次拿箱子之后不选这个箱子,之后没有不拿的机会了，所以就选两个算期望
double avge = sum[0] * 2 / n;
//cout << "avge:" <<avge << endl;
//第一次拿了一个后计算期望，与不拿的时候比较期望
//f[i]：对第i个数而言，如果拿了它，在剩下的n-1个数中，还有一次“不拿”的机会，最终期望的最大值
//res = max(f[i] + a[i], avge)
double res = 0;
for(int i = 0; i < n; i ++)
{
//如果说，第二次选的箱子也不拿，那么剩下n-1的个箱子的期望就是平均值了
double avge1 = (sum[0] - a[i]) / (n - 1);
//cout << avge1 << endl;
//批量处理第二个箱子，暴力的话会超时
int id = lower_bound(a , a + n , avge1) - a;//找到第一个大于等于均值的数的下标
//cout << "id: " <<id <<endl;
double E = sum[id] + avge1 * id;
if(a[i] >= avge1) E -= a[i];
else E -= avge1;
E = E / (n - 1);
res += max(avge, E + a[i]);
}
// res 是所有可能取法期望的总和，所以最后要除以n
printf("%.7lf", res / n);
return 0;
}
京公网安备 11010502036488号