首先这里点名\(\rmWQS\)二分还有决策单调性，但是今天就不写这个了，今天学了一些进阶的东西。闵可夫斯基和这个东西时是用来优化一类凸函数卷积的，一般就是背包或者分治时使用。最常用的是\((\max/\min,+)\)卷积。首先考虑这个卷积式：\(f_k=\max_{i+j=k}\{g_i+h_j

 Welcometo9ilk'sCodeWorld    (๑•́₃•̀๑) 个人主页:    9ilk(๑•́₃•̀๑) 文章专栏：   算法Journey 

原题链接题目大意：采药，每种药只有一株，每株有它的价值和采它所需的时间，现时间有限，请你输出在有限时间内能获得的价值最大是多少。分析：1.这是一个典型的01背包问题（DP）01背包问题的典型特征：有一个限定容量的背包（对应本题中的时间），有物品（每种只有一个）（对应本题中的药株），物品有

原题链接题目大意：棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：向下或向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。棋盘用坐标表示，AA点(0,0)、BB点(n,m)，同样马的位置坐标是需要给出的。现在要求你计算出

分治优化DPLink\(\text{Para.1}\hspace{0.2cm}\)四边形不等式对于形如\(\text{dp}[i][j]=\min_{k<j}{\text{dp}[i-1][k]+\text{cost}[k+1][j]}\)的形式，若\(\text{cost}\)满足\(\text{cost}[a][c]+\text{cost}[b][d]\leq\text{cost}[a][d]+\text{cost}[b

题目思路描述动态规划状态定义：costs[i][j]表示第i个房子粉刷成第j种颜色的花费。dp[i][j]表示前i个房子粉刷到第i个房子为第j种颜色的最小花费。状态转移方程：dp[i][j]=costs[i][j]+min(dp[i-1][k])，其中k!=j。即当前房子的颜色不能与前一个房子

前情提要这个菜鸡CF上了\(\color{darkcyan}Specialist\)，心情大好，正好赶上放假，决定打一场CF。赛时记录A上来脑子抽了，吃了一发罚时。发现写错了一种情况，改过来就过了。感觉并不是一个好的开始。B竟成为本人唯一一遍过的题，虽然写的时候有点慌。CDP。一开始认为空间不够，但发

引言在本章中，我们将尝试解决那些使用其他技术（例如分治法和贪心法）未能得到最优解的问题。动态规划（DP）是一种简单的技术，但掌握起来可能比较困难。识别和解决DP问题的一个简单方法就是尽可能多地解决各种问题。“编程”一词与编码无关，而是源自文献，意思是填充表格，类似于线性规划。

赛时三题，\(D\)就差一个显然的剪枝就能过了，qwq...A显然第一步能选偶数就选偶数，之后只能选奇数。细节见代码。codeB对于选取的任意四条边，设腰为\(x\)，短边为\(a\)，长边为\(b\)，则能形成等腰梯形的充要条件为：\(x\)出现次数\(>=2\)，且\(a+2*x>b\)。两个腰选最大，并且\(a，b\)尽可能接近

[蓝桥杯2023省B]接龙数列原题链接：P9242[蓝桥杯2023省B]接龙数列解题思路计算去掉的数量不好思考，可以先算出最长的接龙数列长度，与\(n\)相减即为答案。考虑使用动态规划计算。令\(dp_i\)为以\(i\)结尾的最长序列，枚举到\(a_i\)时：设\(a_i\)开头数字为\(p\)

目录绿色通道最大连续和修剪草坪旅行问题绿色通道已经讲了好多遍了（2025/1/11，2024/12/21），现在详细捋一下思路首先上来，最有辨识度的就是“最长”空题段“最小”就是最大值最小——二分答案木材加工闻着味就过来了（详见2024/12/28）但这还和木材加工不太一样，check部分不

链接https://www.luogu.com.cn/problem/P1006题目思路和方格取数差不多,额外的步骤就是去重：只取当前节点(i,j)的右上或者左下部分。并且最后的答案是dp[m][n-1][m-1][n],只dp到终点的上面和左边一个点代码#define_CRT_SECURE_NO_WARNINGS#include<iostream>#include<a

F\(dp\)+组合数学需要注意，数组中\(>1\)的数字个数不会超过\(log_{2}k\)个。先暂时不考虑\(1\)的摆放，只考虑所有\(>1\)的数：设\(f_{l,i}：\)长度为\(l\)，乘积为\(i\)，且所有元素均\(>1\)的数组个数考虑数组的最后一个元素\(d\)，必有\(d|i\)成立，因为每个元素一定是\(i\)的因子。则

AtCoderGrandContest001-AtCoder.CDEF看了题解才会。2025.1.17打比赛、补题。2025.1.18写题解。A简单贪心，排序后相邻的放一起。B有点吓人，但是画图手玩一下就可以看出，除了开头和结尾，每一轮是在走一个平行四边形，于是递归。类似辗转相除法求\(\gcd\)递归算一下（不是

AtCoderGrandContest002-AtCoder.EF赛时不会，ENekopedia给我讲了，F看了题解。2025.1.18打比赛、补题、写题解。A随便分讨一下。有一种是看\((b-a+1)\)的奇偶性。可以按\(a<0,a=0,a>0\)来先对\(a\)分类，再分讨对应的\(b\)。总结：注意思路清晰点，分讨要有条理，不要

书接上文树上倍增的具体实现其实树上倍增大致可以分为三个步骤。dfs预处理倍增数组设dp[x

这道题目是打家劫舍III（HouseRobberIII），是打家劫舍系列问题的变种。问题描述如下：小偷发现了一个新的区域，这个区域的所有房屋排列类似于一棵二叉树。如果两个直接相连的房屋在同一晚被打劫，房屋会自动报警。给定这棵二叉树的根节点root，求在不触发警报的情况下，小偷能够盗取的最

链接https://www.luogu.com.cn/problem/P1004题目思路dp思路：如果是走一遍,很显然可以发现(i,j)的值只与(i-1,j)和(i,j-1)有关。于是递推：dp[i][j]=max(dp[i-1][j],dp[i][j-1])+mp[i][j]当走两遍：转换为四维dp:dp[i][j][k][l]。当(i==j&&k==l)时,减去mp[i][j]。代码#de

题目如下数据范围典型的动态规划题。令f(i,j)为以i,j为右下角左边正方形的最大边长,当且仅当f(i,j)>0（即矩阵(ij)不为’0’）时f(i,j)=min(f(i,j-1),f(i-1,j-1),f(i-1,j))对这个方程不太理解的话借用leetcode官方的图也就是说边长为n的正方形可以由3个

1引入插头dp是一种基于连通性状态压缩的动态规划，这一类问题要求我们记录元素的联通状况，例如在棋盘上走出一条回路等。此时朴素的状压dp难以处理，所以需要引入插头dp帮助我们求解。开始前需要了解两个基本概念：轮廓线：已决策状态和未决策状态的分界线。插头：对于四连通的网

【N】新本格魔法少女好题分享1月6日好题分享-安师大附中-VirtualJudgeP11365[Ynoi2024]新本格魔法少女りすか-洛谷记录详情-洛谷这是一道卡常分块题。直接对序列分块，则计算贡献分为如下情况：（不妨设块长为\(B\)）散块对散块：直接用树状数组统计顺序对，复杂度\(O(nB\l

LuoguP1192台阶问题Link简要题意：给定台阶数\(n\le1e5\)和一步至多跨越台阶数\(k\le1e2\)，初始在\(0\)级，求方案数\(\pmod{1e5+3}\)。思路：设\(f_i\)表示走到第\(i\)级台阶的方案数，题意直接说明了可以从前\(k\)级台阶转移过来，考虑每次在以经处理好的台阶前新加一级

定义插入\(\text{dp}\)适用于计数、求最优解且具有选择、排列元素过程等题目。插入\(\text{dp}\)大致分为两类：乱搞型：状态定义天马行空，但始终围绕着将新元素插入到旧元素已有集合中套路型：\(dp_{i,j}\)表示前\(i\)个数，现在构成\(j\)个连续段的方案数\(/\)最优解，此外

LIS与LCS是动态规划中最常见的两种情况，LIS也就是最长上升子序列，而LCS是最长公共子序列。在解决这个问题之前，先要明白为什么是序列，举个例子来说明，在数组[1,2,3,4,5,6]中，[2,3,5]就是其子序列，也就是说，子序列其实就是数组中存在先后顺序，但不强调连续的子数组。那么，在了解了序列是什

（标题就叫这个吧，我也没什么主意了）动态规划，要给这个这个东西下个定义，确实不太好下，他是一种基于状态来思考问题的算法思想用来表示状态的话，那就是dp，（这么说好抽象），就直接说涉及动态规划的题目怎么处理吧，这个还是有步骤可行的，就按如下步骤操作1.寻找子问题2.找出状态转移方程3.最