AcWing 286. 选课,《算法竞赛进阶指南》

2023-10-03 21:46

本文主要是介绍AcWing 286. 选课,《算法竞赛进阶指南》,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

286. 选课 - AcWing题库

学校实行学分制。

每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。

学校开设了 N 门的选修课程,每个学生可选课程的数量 M 是给定的。

学生选修了这 M 门课并考核通过就能获得相应的学分。

在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其他的一些课程的基础上才能选修。

例如《Windows程序设计》必须在选修了《Windows操作基础》之后才能选修。

我们称《Windows操作基础》是《Windows程序设计》的先修课。

每门课的直接先修课最多只有一门。

两门课可能存在相同的先修课。

你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修条件。

假定课程之间不存在时间上的冲突。

输入格式

输入文件的第一行包括两个整数 N、M(中间用一个空格隔开)其中 1≤N≤300,1≤M≤N。

接下来 N 行每行代表一门课,课号依次为 1,2,…,N

每行有两个数(用一个空格隔开),第一个数为这门课先修课的课号(若不存在先修课则该项为 0),第二个数为这门课的学分。

学分是不超过 10 的正整数。

输出格式

输出一个整数,表示学分总数。

输入样例:
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出样例:
13

 解析:

这道题的状态转移方程并不难,关键是注意体积从大到小遍历,因为这是一个分组背包问题

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 305;
vector<int>G[N];
int n, m;
int f[N][N], w[N];void dfs(int a) {for (int i = 0; i < G[a].size(); i++) {int p = G[a][i];dfs(p);for (int j = m-1; j > 0; j--) {for (int k = 1; k <= j; k++) {f[a][j] = max(f[a][j], f[a][j - k] + f[p][k]);}}}for (int i = m; i > 0; i--) {f[a][i] = f[a][i - 1] + w[a];}
}int main() {scanf("%d%d", &n, &m);for (int i = 1, a; i <= n; i++) {scanf("%d%d", &a, &w[i]);G[a].push_back(i);}m++;dfs(0);cout << f[0][m] << endl;return 0;
}

这篇关于AcWing 286. 选课,《算法竞赛进阶指南》的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/759

相关文章

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Java使用Mail构建邮件功能的完整指南

《Java使用Mail构建邮件功能的完整指南》JavaMailAPI是一个功能强大的工具,它可以帮助开发者轻松实现邮件的发送与接收功能,本文将介绍如何使用JavaMail发送和接收邮件,希望对大家有所... 目录1、简述2、主要特点3、发送样例3.1 发送纯文本邮件3.2 发送 html 邮件3.3 发送带

IDEA连接达梦数据库的详细配置指南

《IDEA连接达梦数据库的详细配置指南》达梦数据库(DMDatabase)作为国产关系型数据库的代表,广泛应用于企业级系统开发,本文将详细介绍如何在IntelliJIDEA中配置并连接达梦数据库,助力... 目录准备工作1. 下载达梦JDBC驱动配置步骤1. 将驱动添加到IDEA2. 创建数据库连接连接参数

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

Java中使用注解校验手机号格式的详细指南

《Java中使用注解校验手机号格式的详细指南》在现代的Web应用开发中,数据校验是一个非常重要的环节,本文将详细介绍如何在Java中使用注解对手机号格式进行校验,感兴趣的小伙伴可以了解下... 目录1. 引言2. 数据校验的重要性3. Java中的数据校验框架4. 使用注解校验手机号格式4.1 @NotBl

使用Java发送邮件到QQ邮箱的完整指南

《使用Java发送邮件到QQ邮箱的完整指南》在现代软件开发中,邮件发送功能是一个常见的需求,无论是用户注册验证、密码重置,还是系统通知,邮件都是一种重要的通信方式,本文将详细介绍如何使用Java编写程... 目录引言1. 准备工作1.1 获取QQ邮箱的SMTP授权码1.2 添加JavaMail依赖2. 实现

MySQL进阶之路索引失效的11种情况详析

《MySQL进阶之路索引失效的11种情况详析》:本文主要介绍MySQL查询优化中的11种常见情况,包括索引的使用和优化策略,通过这些策略,开发者可以显著提升查询性能,需要的朋友可以参考下... 目录前言图示1. 使用不等式操作符(!=, <, >)2. 使用 OR 连接多个条件3. 对索引字段进行计算操作4

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配