一.题意 n*m 的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * 2 ^ i ，i 为第 i 次取数且每次取走的各个元素只能是该元素所在行的行首或行尾，取 m 次，求取数的最大得分和。 二.题解 因为每次只能取行首或者行尾，所以每行取得顺序都是独立的。由此可以从 求最大的得分和 转换成 求每行的最大得分和。如何求每行的最大得分和?可以发现肯定是从一个长度为 1 的区间扩展到 长度为 n 的区间。所以我们可以用区间 dp 来求解。设 dp[l][r] 来维护 l ~ r 区间的最大得分。转移方程: 这里的 x 为第几次取数。这题还要注意数据会爆longlong ， 所以必须...

一.题意 有N件商品，有利润pi和过期时间di，每天只能卖一件商品，过期商品不能再卖，求最大收益是多少。 二.题解 对于这题，很明显是贪心，肯定是取价格高的物品，但是还要考虑过期时间。本来是可以考虑枚举过期时间，然后在同一过期时间选择价格最高的物品，但其实这样是不对的。例如:450 160 1100 2200 2可以发现选择过期时间为 2 的两件物品可以取到最高价格，所以考虑同一时间价格最高是不对的。这个时候我们只需要在前面的策略上加上反悔机制即可。类似于如果发现前面有物品的价值比他还小，说明可以用该物品替换，这个可以用优先队列优化。所以可以按照过期时间从小到大排序，这样的话后面如果有价值更大...

一.题意 n * m 的矩阵分成 k 组互不重叠的矩阵，求最大的子矩阵和。 二.题解 特别注意到的是 m 的值为 1 或者 2，所以可以由比较简单的方法写出。考虑 代表第一列前 i 个元素和第二列前 j 个元素组成 k 个矩阵的最大值。有以下的递推方程: 由前一状态推出， 枚举第一列， 枚举第二列， 当第一列和第二列取同样多的元素可以考虑合并， 三.代码: #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ld long double #define ll long long...

一.题意 将一组物品分成两组，每个物品都可以不出现在任何一组。希望两组的重量差异不超过M，求最大化总重量。 二.题解 首先明显的背包，不过第二维代表的含义稍微做了点修改， 代表选取前 i 个物品重量差不超过 j 的最大总重量，那么很明显的有: 不选取第 i 个物品: 选取第 i 个物品并放在天平较重的一边 : 选取第 i 个物品并放在天平较轻的一边，同时考虑这个较轻的一边总重量可能会超过另一边，所以需要加上绝对值: 当然这题最重要的就是注意初始化，把 dp 数组初始化为一个很小的数，同时设 ，保证所有状态的 dp 都是由 0 推出。 三.代码: #include<bits/st...

一.题意 德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西亚英雄的方法？ 二.题解 首先 表示第 i 行状态为 j 的合法方案数，然后考虑一行一行枚举下去，当前行的合法方案由上一行的合法...

一.题意 这道题要求小A和小B最早的相遇时间。而小A的行走规则是：每次可以走8个方向，每次走一步。小B的行走规则是：每次可以走4个方向，但每次走两步（两步不一定是要同方向）。 二.题解 很明显分别对两个人进行bfs 计算出到达每个点两个人到达的最短时间然后枚举两个人都能达到的点，比较取较大值，再与ans 取较小值但是我不知道为什么一直有百分7的样例过不去所以我参考了部分题解，用了另一种方法类似于分层图，对两个人在两张地图同时bfs，在n*m步内有答案即输出，否则no，详细可见代码。 代码: #include<bits/stdc++.h> #define mp make_pair #...

一.总结 懵了，全都不会，应该都不是正解，全是黑科技操作。 二.题解 A.拯救咕咕咕之史莱姆 正解的话应该是根据题目模拟计算第 6 天的 hp。我的话直接观察样例，发现 73 可以但是 77不可以故说明答案的分界线就在 74~76之间，最多 wa 3次就可以A，故从76开始，没想到一发就A了。 代码: #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #define fi first #define se second #define inf 0x3f3f3f...

一.总结 后面开始打的，很多题都不是正解，都是歪门邪道/奇淫技巧，看了官方题解才恍然大悟，这里给大家介绍一下跟正解不同的黑科技做法。 二.题解 A. 怪盗-1412 一开始再由于子序列的问题，想了想第一个例子觉得不可能只是504，所以觉得自己读错题了，只能反着从样例读题。 很明显第一个例子是 6 ，7 ， 8 ， 答案是 504 。因为1412中的4和2都是单一的，所以必须会相乘并成为答案的一部分，所以我尝试用504/7/8，求出9，不难联想到9是3*3，正好是6的一半。 所以答案的式子就有了： 代码: #include<bits/stdc++.h> #define mp mak...

一.总结 兰子姐姐的题还是比较能够让人看到希望的，但是由于 cout double 的 bug ，在F和G浪费了太多时间，还有各种细节都没注意到，都没时间做完。 本次怀疑人生：F/G/J 二.题解 A.AOE还是单体？ 样例的解释明显告诉我们如何去计算，就是判断使用一次群体攻击的花费是否大于单独攻击 k 次的花费，然后我们就可以根据 x 来决定使用多少次群体攻击。 代码: #include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #define fi first #d...