动态规划——树形DP学习笔记引入前置知识：树基础。树形DP，即在树上进行的DP，最常见的状态表示为\(f_{u,\cdots}\)，表示以\(u\)为根的子树的某个东东。本文将讲解一些经典题目（树的子树个数、树的最大独立集、树的最小点覆盖、树的最小支配集、树的直径、树的重心、树的中心），以及一些常见形式及思路（树上背包、换根DP）。目录分类树的子树个数树的最大独立集树的最小点覆盖树的最小支配集树的直径树的重心树的中心经典问题１：最小化最大距离树上背包换根DP分类树形DP问题的划分方法有多种方式。按照「求解目的」进行划分选择节点类：在树上进行选择，相邻节点不允许同时选；树形背包类：在树上进行背包
「学习笔记」数位DP意义不大的题不写了。点击查看目录目录「学习笔记」数位DP概述例题P2657[SCOI2009]windy数思路代码P4317花神的数论题思路P4124[CQOI2016]手机号码思路代码haha数题意思路代码0和1的熟练题意思路代码苍与红的试炼题意思路代码概述数位DP一般用来解决「在一个较大的区间内统计具有一定特征的数的数量」的问题。数位DP一般有两种做法：递推法：首先需要预处理出具有一定条件的数的个数，然后将上限按数位拆分开来考虑贡献。暴搜法：直接记忆化搜索具有特定条件的数的个数。例题P2657[SCOI2009]windy数思路本题使用递推。设\(f_{i,j}\)表示
动态规划——带权二分优化DP学习笔记引入带权二分其实并不一定用于优化DP，也可能用于优化贪心等最优化的算法。带权二分也叫WQS二分，最初由王钦石在他的2012年国家集训队论文中提出。定义使用情况要解决一个最优化问题（求最大/最小值）有一个限制，一般是某个参数要求一定恰好为\(k\)而带权二分就可以很好的解决［恰好\(k\)个］的限制；以选物品取最大收益为例：设\(f(k)\)为恰好选\(k\)个时的最大收益，将所有的\((k,f(k))\)画出来，图像必须组成一个凸包。因此就可以打表看，是否组成了一个凸包，如果是，则可以考虑带权二分优化。使用方法例：求\(f(k)\)的值，我们不会求\(f(k
比较套路的题目首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况：我们发现第3个人没了，所以可以出现跨2的情况然后直接上dp，由i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3转移过来。然后这显然可以拿矩阵表示。然后显然可以拿线段树维护。后面三部分都是比较套路的。#includeusingnamespacestd;#defineintlonglonginlineintread(){intx=0,f=1;charch=getchar();while(ch'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();
我们一路奋战，不是为了改变世界，而是为了不让世界改变我们。目录我们一路奋战，不是为了改变世界，而是为了不让世界改变我们。动态规划——DP算法（DynamicPrograming）一、🏔斐波那契数列（递归VS动态规划）1、🐒斐波那契数列——递归实现（python语言）——自顶向下2、🐒斐波那契数列——动态规划实现（python语言）——自底向上二、🏔动态规划算法——思想简介1、🐒DP算法思想2、🐒DP算法——解决问题的基本特征3、🐒DP算法——解决问题的基本步骤 4、🐒求解例子——求阶乘n!三、🏔动态规划——常见例题1、🐒求解最长不降子序列2、🐒求解最长的公共子序列获取源码？私信？关注？点赞？收
做了几个移动端的项目之后，深感UI设计移动端尺寸换算的必要性，在此做个总结。先介绍下各自的定义：px：pixel，像素，电子屏幕上组成一幅图画或照片的最基本单元pt:point，点，印刷行业常用单位，等于1/72英寸ppi:pixelperinch，每英寸像素数，该值越高，则屏幕越细腻dpi:dotperinch，每英寸多少点，该值越高，则图片越细腻dp:dip，Density-independentpixel,是安卓开发用的长度单位，1dp表示在屏幕像素点密度为160ppi时1px长度sp:scale-independentpixel，安卓开发用的字体大小单位。以下是换算关系：一、pt和px
背包问题-01背包首先我们要明白什么是01背包，在下述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的\(0\)和\(1\)，这类问题便被称为\(\text{「0-1背包问题」}\)。题目描述有\(N\)件物品和一个容量为\(M\)的背包。第\(i\)件物品的重量是\(W_i\)，价值是\(D_i\)。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。输入格式第一行：物品个数\(N\)和背包大小\(M\)。第二行至第\(N+1\)行：第\(i\)个物品的重量\(W_i\)和价值\(D_i\)。输出格式输出一行最大价值。我们可以设状态\(dp_{i,j
动态规划：两个数组的dp问题前言两个数组的dp问题1.最长公共子序列（中等）2.不同的子序列（困难）3.通配符匹配（困难）4.正则表达式（困难）5.交错字符串（中等）6.两个字符串的最小ASCII删除和（中等）7.最长重复子数组（中等）前言动态规划往期文章:动态规划入门：斐波那契数列模型以及多状态动态规划：路径和子数组问题动态规划：子序列问题动态规划：回文串问题两个数组的dp问题1.最长公共子序列（中等）链接：最长公共子序列题目描述做题步骤状态表示对于两个数组的dp，采用一维dp是没有办法清晰的表示状态的，故对于两个数组的dp我们通常采用二维数组。故定义状态表示为dp[i][j]：s1的[0，
动态规划文章目录动态规划01背包多重背包分组背包区间dp洛谷例题camp训练赛牛客竞赛网两个约束条件最优子结构：为了计算考虑了前i个物品，总体积为j时的最大收益，我们可以先计算考虑了前i-1个物品，总体积为j时的最大收益以及考虑了前i-1个物品，总体积为时的最大收益。知道了考虑了前i-1个物品，总体积为j时的最大收益以及考虑了前i-1个物品，总体积为时的最大收益，我们就能算出考虑了前i个物品，总体积为j时的最大收益。由于在每次拆解过程中我们会少考虑1个物品，最后一定会在有限次拆解后变成一个什么物品都不考虑的子问题，所以在问题拆解过程中不会陷入无限递归。**无后效性：**我们只关心考虑了前i个物
1.0/1背包1.1.算法思路0/1背包是动态规划、背包问题中最经典的问题啦！它主要的问题是：给定n种物品、这n种物品的重量分别是，价值分别是 ，而你有一个容量为C的背包，请问如何求出所能拿的最大价值呢？对于动态规划，我们先需要找到一条推导公式，然后确定边界：我们设dp[i][j]为一个背包，表示前i个物品装入容器为j的背包中可以获得的最大价值。我们可以推导出：dp[i][j]=max(dp[i-1][j],dp[i-1][j- ]+ )也就是说，当前的dp值由装和不装入第i个物品来决定的。不装入第i个是：dp[i-1][j]，装入的话j要减去这个物品的重量也就是： dp[i-1][j- ]+
