DaMing

分类

题解(25)

/ 注册

全部文章（共4篇）

失衡天平（DP）

题目描述：有一个长度为n的序列，从中选择任意个数字将其分成两堆使两堆的和最大（且两堆的差值不超过m）先证明一下取两次转化成一次的正确性假设第一次取了 a ,b第二次取了 c ,da-b=mc-d=m-1那么如果我们把c放在a这端明显是错误的我们把c放在b端( a+d )- (c+b)=-(m...

dp

2020-06-10

2 915

SCOI2005]最大子矩阵(dp)

一开始思路错了，想着把k当成1 求了一个最大子矩阵然后对最大子矩阵所在的一行用最大k段子序列，后来发现思路错了，因为这样所求的子矩阵的终点行一定都相同了正确的思路：因为m（列）是1&amp;amp;lt;=m&amp;amp;lt;=2，只有两种情况，对于m==1时候...

dp

2020-06-07

1 803

B-经商(并查集+01背包)

题目描述任务一：有n个人，每个人只能选一次，会消耗a[i]精力得到b[i]收益，现有的精力值为C,求可以到达的最大收益思路这么看就是一个简单的01背包问题（用一维的话注意从大到小枚举c（精力））任务二这n个人之间存在友谊关系，我们只能选择跟1有关系的人，思路用简单的并查集维护，在01任务1求解的时候...

并查集 dp

2020-06-04

0 778

货币系统（dp/暴力）

题意要求我们构造两个等价的货币系统我们把已知的货币系统中冗余的删掉比如有3 6 那么我么可以删掉6 ，因为6可以用3表示又比如 19 10 3 那么我们可以删掉19 ，因为19=10+3+3+3 首先说说暴力的解法，因为数据范围比较小，对于序列中的每一个数字 a[i] 用dfs去判断能不...

DFS dp

2020-05-30

0 642