Meul

分类

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1) 题解(75)

/ 注册

TA的专栏 13篇文章 1人订阅

11eyes的每日一题

3篇文章 852人学习

11eyes的排位日记

10篇文章 946人学习

0篇文章 0人学习

全部文章（共16篇）

NC14704 美味佳肴

Question 给定n个食物素材和m个食物种类，每个食物素材具有不新鲜度b，每个食物具有特定且唯一的食物素材编号为j，美味值a和做菜所需要的时间c。食物美味值，求T时刻，最大美味值为多少？ Solution 每个食物的美味度只和他完成的时间点有关。两个食物若默认比先做后做的区别在于: 我们对其排序...

DP 01背包

2020-04-28

0 683

NC17065 子序列

Question 一个由n个元素组成的序列，她想知道其中有多少个子序列，满足对于所有的成立。 Solution 盲猜当满足时前后都是单调递增的。严格证明(来源于雨巨的题解！我估计我可能真的做的时候会盲猜试一发，或许这是一种直觉？)然后DP求对应的贡献即可，设表示必选第i个的情况下有多少种满足的取法,...

dp

2020-04-28

0 524

NC51180

题意给定一棵个节点的无向带权树，要你找出一个节点作为根，向叶子节点流水，使流水量最大。思路换根DP这种题往往都是先从某个点出发，求出以这个节点为根的答案，并记录与答案相关的数据到数组中。然后从节点出发，记录换根的答案，其中所有根的最大值就为所求值。难点在于该如何去找寻其中的递推关系式。数组表...

树换根dp DP

2020-04-17

0 642

NC13611

NC13611 题意一棵有n个结点的树，我们有k种不同颜色的染料给树染色。当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同时，染色方案是合法的。请统计方案数。思路把题目转化为给你一颗n结点的树，将其分成个连通块涂上不同的颜色，此时发现染色方案的数量与这棵树...

DP 组合数学

2020-04-10

0 716

NC22598

NC22598 题意（题目数据范围M=N-1可知这是一棵树，一个边数为结点数-1的连通图一定为一棵树）给你一颗N个结点的树和对应边的权值，求以S结点为根节点去掉一些边使得不与叶子结点直接相连的最小代价为多少？思路第一次做树形DP，设为结点的度为多少，重要结论：叶子结点的度一定为1，结合根节点的...

树形DP DP

2020-04-02

0 541

NC4853C

题意由小写英文字母组成的长度为n的一个字符串，求不相同的长度为k的子串的数量对1e9+7取模。思路正难则反正难则反，我们求所有不同的子串，不如把所有子串的数量求出来再减掉所以相同的子串数量。若不去重求所有长度为k的子串的数量，则可由推出到第个数为止长度为的子串数量。不难理解,代表的是到...

DP

2020-03-28

4 809