leetcode 956. 最高的广告牌「动态规划」
用差值状态压缩理解最高的广告牌。
174. 地下城游戏「动态规划」「逆向思维」
174\. 地下城游戏https://leetcode.cn/problems/dungeongame/ 题目描述： 二维矩阵，每个点都有一个价值，起点是左上角1, 1，终点是右下角n, m，初始价值为一个未知的正整数，每次只能往下或者往右
AtCoder Beginner Contest 307「E dp」
E Distinct Adjacent 题目描述： 给两个数n和m，求一个长度为n的排列的数量，排列要满足如下条件： a\i\ = 0 && a\i\ <= m，即a\i\可以是0到m1中任意的一个数 任意相邻数字不能相等，同时a\1\不能
ARC133 B - Dividing Subsequence
B Dividing Subsequencehttps://atcoder.jp/contests/arc133/tasks/arc133b?lang=en 题目描述： 两个序列ar,br,分别选择k个数，满足bri % ari == 0,
L3-2 拼题A打卡奖励 (30 分)「01背包优化」
L32 拼题A打卡奖励 30 分https://pintia.cn/problemsets/1515651913806946304/problems/1515651986691366925 题目描述： n张卡片，每张卡片有一个花费cost，
abc147_E - Balanced Path「dp」
E Balanced Pathhttps://atcoder.jp/contests/abc147/tasks/abc147e?lang=en 题目描述： n m的矩阵，每个矩阵上有两个值，一个a,一个b，这个点的价值是ab或者是ba，问从
有依赖的背包问题「树上分组背包」
有依赖的背包问题 题目描述： n个物品，容量为m,物品之间有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大 求最大价值 思路： 如果考虑每个子
最长公共上升子序列「LIS」「LCS」
最长公共上升子序列 题目描述： 给两个数组a和b 问两个序列的最长的公共上升子序列的长度 思路： 状态：dpij表示a数组的前i个，b数组的前j个中以brj为结尾的公共上升子序列的最大长度 转移方程可以将最长公共子序列和最长上升子序列结合起
AtCoder Beginner Contest 244 E - King Bombee 「图论 + dp」
E King Bombeehttps://atcoder.jp/contests/abc244/tasks/abc244e 题目描述： n个点，m条边，求起点是s，终点是t，经过偶数次点x的长度为k+1的路径的数量 思路： dpijk表示从
AtCoder Beginner Contest 236 E - Average and Median 「二分答案 + dp」
E Average and Medianhttps://atcoder.jp/contests/abc236/tasks/abc236e 题目描述： 给定一个长度为n的序列，从中按要求挑选若干个数 对于所有的i，都必须从ai，ai+1中至少
树形dp
树形dp 树形dp，即在树上进行的 dp。由于树固有的递归性质，树形 DP 一般都是用dfs来递归进行的。 主要的思路就是计算子树，然后合并 模版大概是这样的 题型一般分为两种：选择节点类、树形背包类 选择节点类 选择节点式的题，首先前提条
万字背包详解
前言： 古有陈天华万字血书抗沙俄，今有本剧蒻万字背包虐dp 本文介绍了01背包、完全背包、多重背包、混合背包、分组背包等背包，并对其进行透彻的剖析，并附上了板子题，供您白嫖，以及一些奇葩变式，颇有意思，供你琢磨玩弄。此外绝大部分题都有二维数
leetcode 1937. 扣分后的最大得分「动态规划」「拆项」
1937\. 扣分后的最大得分https://leetcode.cn/problems/maximumnumberofpointswithcost/ 题目描述： 给你一个nm的整数矩阵ar，一开始你的得分为0，你想最大化从矩阵中得到的分数
AtCoder Beginner Contest 229 「F dp」
F Make Bipartitehttps://atcoder.jp/contests/abc229/tasks/abc229f 题目描述 给出n+1个点，下标是0到n，从1到n都存在一体指向0的带权无向边，边权为ar\i\，同时从i到i+
900.整数划分「完全背包计数」
整数划分 题目描述： 一个正整数n可以表示成若干个正整数之和，如：n = n\1 + n\2 + n\3+...+n\k 其中 n\1≥n\2≥...≥n\k,问n存在多少种不同的划分方式 思路： 动态规划的计数问题 由于一个数字可以用很多
Lemonade Trade「dp + 对数优化」
Lemonade Tradehttps://codeforces.com/gym/101666/attachments 题目描述： 你有一升粉色饮料，想换取蓝色饮料 有n个商人，每个商人可以将1升b饮料换成p升a饮料，p是汇率，只能从1到n
arc070_D - No Need 「二分答案 + dp check」
D No Needhttps://vjudge.net/contest/488154problem/L 题目描述： n个数字，求有多少个数是不必要的数字 不必要数x的定义是： 对于所有包含x序列、且序列和大于等于k的子序列，我们删掉x后，序
第十二届蓝桥杯省赛第一场C++「砝码称重」
砝码称重https://www.acwing.com/problem/content/3420/ 题目描述： 你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,···,WN。 请你计算一共可以称出多少种不同的正整数重量？ 注
二维费用的背包问题
二维费用的背包问题https://www.acwing.com/problem/content/8/ 题目描述： N件物品，容量是V的背包，背包能承受的最大重量是M 每件物品只能拿一次，体积是vi，重量是mi，价值是wi 问在容量和重量允许
导弹防御系统 「LIS + DFS」
导弹防御系统https://www.acwing.com/problem/content/189/ 题目描述： 为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。 一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单
AtCoder Beginner Contest 238 F - Two Exams「dp + 二维偏序」
F Two Examshttps://atcoder.jp/contests/abc238/tasks/abc238f 题目描述： n个考生，参加了两次考试，第一次的排名是Pi，第二次是Qi,现在需要选m名考生去参加活动，必须保证不能存在未
刷墙「区间dp」
U187635 刷墙easyhttps://www.luogu.com.cn/problem/U187635?contestId=56041 题目描述： n面墙，每面墙都有一个颜色，k个工人，每个工人至少刷一面墙，每个工人不是白干活，需要支
区间dp
石子合并https://www.acwing.com/problem/content/description/284/ 题目描述： 设有 NN 堆石子排成一排，其编号为 1，2，3，…，N1，2，3，…，N。 每堆石子有一定的质量，可以用一