并查集+转化成序列DP O(n*m)

数据有环要小心

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

并查集。。。搞懂了就，it is so easy!

+降一维分组包

并查集少打j:=get(i);

太晕了!!!!!!!!!!!!!!!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

纪念一下

分组背包可以降维的

for i:=1 to n do

for j:=w downto 0 do

for k:=1 to a[0] do

i为i组物品

w为背包容量

k为每组的物品数

一定注意循环的嵌套　

分组背包不能降维吗？？好像不能吧。。。

查了半天..忘记跟自己对比了- -(原来有写的..然后优化来优化去把关键语句给删了..自己还不知道...=- -||||||)

可以参考DD_engi神牛的背包9讲!

分组的背包+并查集

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

好简单啊。

根据冲突的物品，可以由原问题可以构造出一个分组的背包问题（利用并查集），做法可以见“背包问题九讲”

这题使我崩溃了。

并查集+背包

a表示以i为根的第j个物品的属性

f:=max{f[i-1,j-a.w]+a.p,f}

dp 即可 求解

From 疾风剑客

最勇敢的机器人 Wind~机器人系列 系列

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DP+并查集

答楼下:

"并查集+背包

h表示以i为根的第j个物品的属性

f:=max{f[i-1,j-h.w]+h.p,f"

哪位大牛能否解释下上面的方程?

什么叫 h表示以i为根的第j个物品的属性?

K表示什么?>??

k表示取第i个集合中的第k个元素,i表示第i个集合,j表示背包容量

欧！这题快做的吐了！！最后并集的时候忘记找爸爸了！！

把所有放到一起要爆炸的物品并入一个集合，然后以集合划分阶段，枚举集合中的每个物品

"并查集+背包

h表示以i为根的第j个物品的属性

f:=max{f[i-1,j-h.w]+h.p,f"

哪位大牛能否解释下上面的方程?

什么叫 h表示以i为根的第j个物品的属性?

K表示什么?>??

详见 wind机器人大赛 解题报告。

注意赋初值时把所有不存在的状态都覆盖到！

谁能贴个程序出来借鉴借鉴

我总是只能过2个点