dp
-
P3177 树上染色做题记录
树形 dp 好题。 做这题的思想历程： 定义 /(dp_{i,j}/) 表示以 /(i/) 为根的子树中，选择了 /(j/) 个节点的答案。感觉还要带上一维状态就是所有黑点距离 /…
-
Mondriaan's Dream(状压dp)
Mondriaan’s Dream(状压dp) 题目大意：用1×2的方块填满NxM的大矩形，问填满的方法有多少种。解题思路：利用先填好竖着的方块，剩下的空格再…
-
UVA11584 划分成回文串 Partitioning by Palindromes
题面 这道题一开始想用简单的区间DP #include<stdio.h> #include<iostream> #include<cs…
-
2022.9.8模拟
100 + 100 + 40 = 240 ptsT1 T2很水…T3怎么说呢，我没有想到如何来dp，所以写了一个大膜你的贪心，骗了40分，虽然显然是假的。那正解的dp是…
-
优化dp
单调队列优化dp 单调队列 单调队列是一种特殊的双端队列，其内部元素具有单调性。常见有最大队列和最小队列两种单调队列，其内部元素分别是单调递减和单调递增的。 支持两种操作 -插入：…
-
remake(DP)—数位dp篇
模板总结 寄搜模板 ll dp[N][state]; // 状态根据题目性质改变, 例子记录数位中 非零 数位的个数 // 从高位向低位递归 ll dfs(int pos, int…
-
leetcode 45 跳跃游戏 最少次数 C/C++ 动态规划
动态转移方程 dp[pos] = min{dp[pos-k] +1} 当a[pos-k] >= k , k 是两次状态之间a的物理距离。 动态规划并不是这个例…
-
数位dp
数位dp 目录 数位dp 简介 题 同类分布 /(/text{Balanced Number}/) 简介 数位 /(dp/) 是一种在数位上进行的 /(dp/)，通常用于解决值域 …
-
LeetCode — 最小路径和
LeetCode — 最小路径和 问题陈述 给定一个 mxn网格 用非负数填充，找到一条从左上角到右下角的路径，该路径最小化沿其路径的所有数字的总和。 笔记： 您只能在任何时间点向…
-
多重背包问题 II
多重背包问题 II(水题但有注意点) 二进制优化的多重背包问题（主要注意的是二进制优化后的数组的大小问题） AC代码 #include <cstdio> #includ…