yxy

用户名：dotcpp0787179

访问量：497

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	976
经　　验	3389
参赛次数	3
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣
浏览：56

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：38

你可能喜欢

[搭配购买(buy)] 并查集 + dp动态规划（一维优化版）

　　作者: yxy　　　　发表时间：2024-09-18 15:36:19 浏览：24　|　评论：0　

原题链接：搭配购买(buy)

# 并查集 + 动态规划一维优化
###### 分析题目 所有的云朵都有关联 可以联想到并查集 将所有的相关元素全部存进根节点 并将其视为一个大的连通块（整体）
###### 同时 又是一眼的dp模型 （01 背包模型）
##### 思路就很清楚了 在前n个物品中 花费x元 买到价值最大的组合

###### 状态转移方程 ： f[j] = max(f[j] , f[j - v[i]] + w[i]);
###### 此处v为云的价格 w为云的价值

###### Code：
```cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long  //个人习惯 有备无患

using namespace std;
const int N = 100010;
int n , m , mo; //n为云的个数 m为相关联的组数 mo为J的钱
int p[N] , f[N]; //p为并查集数组 f为动态规划数组
int w[N] , v[N];//w为云的价值 v为云的价格

int find(int x)  //查
{
    if (x != p[x]) p[x] = find(p[x]);

return p[x];
}
signed main()
{
    cin >> n >> m >> mo;
    for (int i = 1 ; i <= n ; i ++ ) cin >> v[i] >> w[i] , p[i] = i;//初始化p 为每个云都是自己的根节点

for (int i = 1 ; i <= m ; i ++ )
    {
        int a , b;
        cin >> a >> b;
        int pa = find(a) , pb = find(b);
        if (pa != pb)
        {
            p[pa] = p[pb]; //并
            w[pb] += w[pa]; // 将关联的云的价格 价值 全部存在根节点 并视为整体
            v[pb] += v[pa]; //同理
        }
    }

for (int i = 1 ; i <= n ; i ++ ) //动态规划
        {
            if (p[i] == i) //找到根节点 
            {
                for (int j = mo ; j >= v[i] ; j -- )
                {
                    f[j] = max(f[j] , f[j - v[i]] + w[i]); //状态转换
                }
            }
        }

cout << f[mo] << endl; //输出答案
    return 0;
}
```
### 题解不宜 更多题解点主页！

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

yxy

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

校门外的树（C++代码）

开心的金明（C++代码）

C二级辅导-同因查找（C语言代码）

妹子杀手的故事（C语言代码）

[搭配购买(buy)] 并查集 + dp动态规划（一维优化版）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.2 （Java代码）

这可能是一个假的冒泡法

P1001 （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

WU-输出九九乘法表（C++代码）

IP判断（C语言描述，蓝桥杯）

1113题解

简单的a+b （C语言代码）

字符串的输入输出处理（C语言代码）

yxy

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

校门外的树 （C++代码）

开心的金明 （C++代码）

C二级辅导-同因查找 （C语言代码）

妹子杀手的故事 （C语言代码）

[搭配购买(buy)] 并查集 + dp动态规划（一维优化版）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.2 （Java代码）

这可能是一个假的冒泡法

P1001 （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

WU-输出九九乘法表 （C++代码）

IP判断 （C语言描述，蓝桥杯）

1113题解

简单的a+b （C语言代码）

字符串的输入输出处理 （C语言代码）

母牛的故事（C语言代码）

校门外的树（C++代码）

开心的金明（C++代码）

C二级辅导-同因查找（C语言代码）

妹子杀手的故事（C语言代码）

　　评论区

WU-输出九九乘法表（C++代码）

IP判断（C语言描述，蓝桥杯）

字符串的输入输出处理（C语言代码）