dp

[51nod1326]遥远的旅途

Description 一张有n个点，m条变的无向图，每条边有边权。在0时刻有一个人在点1，每一次他走过一条边，消耗的时间为这条边的边权，而不能停留在原地。现在他想知道是否存在一种方案使得他在T时刻刚好到达点n。多组数…

[CF 712D] Memory and Scores

###Description 有两个人在玩游戏，第一个人初始有a分，第二个人有b分。总共玩t轮游戏，每一轮游戏每个人可以从[-k,k]中任选一个数，加进自己的分数中。分数大的人获胜。求有多少种情况先手获胜。答案mod 1e97 1 ≤ a, b ≤ …

[UOJ#246][UER#7C]套路

Description 给出n个在[1,m]范围内的数，你需要从中至少选k个连续的数。定义s(l,j)表示[l,r]这个区间中的数两两之间差值绝对值的最小值，你需要让选择的区间[i,j]的s(i,j)*(j-i)最小。求这个最小值。 n,m<2*10^5 Solution 现在我们要想想如何求…

bzoj 4069: [Apio2015]巴厘岛的雕塑

Description 印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。在这条主干道上一共有 N 座雕塑，为方便起见，我们把这些雕塑从 1 到 N 连续地进行标号，其中第 i 座雕塑的年龄是 Yi 年。为了使这条路的环境更加优美，政府想…

POJ 2486 树形dp

题意：一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走V步，最多能遍历到的权值 dp[root][k]表示以root为根的子树中最多走k时所能获得的最多苹果数在经典…

Codeforces 288E Polo the Penguin and Lucky Numbers

题目大意： 我们定义只含有4或者7的数为“幸运数” 现在给你L,R，问你L到R之间的幸运数的和答案对10^97取模 (1<l<r<10^100000) 看到数字第一个想到的就是数位DP。我们用sx[i][4]表示长度为i且开头为4的幸运数的和用sx[i][7]表示长度为…

bzoj 2726: [SDOI2012]任务安排

Description 机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3...N。这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所…

bzoj 1597: [Usaco2008 Mar]土地购买

Description 农夫John准备扩大他的农场,他正在考虑N (1 < N < 50,000) 块长方形的土地. 每块土地的长宽满足(1 < 宽 < 1,000,000; 1 < 长 < 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽,…

[hackerrank random]

Description 给出一个数列{d}，|d|n。依次进行a次操作1和b次操作2。操作1：随机一个二元组(l,r)[l< r]，交换d[l],d[r] 操作2：随机一个二元组(l,r)[l< r]，翻转区间[l,r] 最后随机一个二元组(l,r)[l< r]&a…

POJ - 1088 滑雪（DP+贪心）

链接：https://vjudge.net/problem/POJ-1088 题意：给你n，m，再给一个n*m的矩阵（h[n][m]）。可以往相邻的四个位置走，前提是当前h要大于下一个位置的h，求最长的长度。也就是求最长严格下…

acwing 1052 设计密码

题面题解(DP状态机KMP) KMP匹配过程： 对于模板串我们先提前预处里出ne数组，然后在匹配的时候，如果当前位置的模式串和模板串匹配，那么指针向后移动，如果当前位置的模式串和模板串不匹配，我们就要将模板串的…

2019ACM山东省赛B ZOJ - 4114 Flipping Game

（思路：设dp[i][j]表示的状态为：第i轮有j个与目标状态不同的灯时的方案数。设上一轮有l个不同，那么这一轮我们改变其中x个的状态，然后再改变其余n-l个中y个的状态，那么就有xym&&l-xyj。所以状态转移…

POJ 1155 经典树形dp+分组背包 + 模板

题意：电视台发送信号给很多用户，每个用户有愿意出的钱，电视台经过的路线都有一定费用，求电视台不损失的情况下最多给多少用户发送信号。dp[i][j]代表i节点为根节点的子树j个用户的时候最大剩余费用。dp[i][j] max(dp[i][j], dp[i…

GDSOI 2016 T2 星际穿越

Description 有n个人在排队。他们会按顺序选择自己喜欢的点a[x]。如果a[x]已经被选择了，那么他会选择f[a[x]]，如果f[a[x]]已经被选择了，则选择f[f[a[x]]]…保证所有人都有点选择。求选择的点本质不同的排列的方案数。 n<10^6 Solution …

题面题解代码 #include<bits/stdc.h>using namespace std; const int N 5e4 10; const int INF 1e9;int n, t; int w[N]; int q[N]; int f[N];bool check(int limit) {int hh 0, tt -1;q[tt] 0;for (int i 1; i < n; i) {while (hh < tt && q[hh…

HDU2059，龟兔赛跑（DP）

题中有N个充电站，我们另外添加两个充电站，一个在起点，另一个在终点，则可以定义DP： 状态：dp[i]表示到达第i个充电站所需的最短时间。状态转移方程：dp[i]min(dp[j]T)第j个充电站到第i个充电站的时…

背包问题理解与感悟（DP）

01背包问题： 有n件物品，每件的价值及体积分别为v,w，且最多只能选一个，有一个背包总容量为V，求所选物品总体积不超过V时可获得的最大价值。 1.用二维数组dp[i,j]来处理： 状态：dp[i,j]表示选取前…

北大ACM——3176，Cow Bowling（动态规划）

这道题跟数塔一模一样，运用到逆向思维，还是从数字金字塔的顶端往下走，要求出最终的位置所得到的数字之和最大。思路：从下往上走，而非从上往下走。设置dp[i,j]数组，dp[i,j]表示：当走到&#x…

bzoj 2442: [Usaco2011 Open]修剪草坪

Description 在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在， 新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛…

【SDOI2014】数数

Description 求1~N中不含数字串集合S中的任意一个的数字的数量。数字串可以有前导0，少于位数不用补0. 字符串集合中有M个串，字符集总长为L。 |N|<1200,M<100,L<1500 Solution AC自动机上DP。设Fi,j,up,zero表示当前到第i位&#xff0c…

HDU 4003 树形dp+分组背包

求K个机器人从同一点出发，遍历所有点所需的最小花费注意到，对于某个节点为根节点的子树，如果需要遍历完再回来，一个机器人遍历的花费<多个机器人的花费，所以一开始先用一个机器人遍历再回来，保证有一个…

[校内模拟]为了部落

Description T次询问，每次询问给出n,m,k,P，问n个点的所有有标号生成森林中，连通块数为m的方案中，从每棵树中选择一个度数<k的点的方案数对P取模的方案数 n<10^9,m,k<100 Solution 我们先选关键点，再数生成…

CF296B Yaroslav and Two Strings

分析考虑到整个序列只要有一对不合法的就可以贡献答案，我们可以设计以下几种方案来进行dp 设f[i][j]表示当前位置为 i ，状态为 j 的方案数： j 0 表示前面已经出现不合法的情况 j 1 表示前面都是s小于等于w j 2 表示前面都是s大于…

[洛谷P4707]重返现世

Description 有n种物品，每次操作你有pimpi\over mmpi的概率获得第i种物品求你获得k种物品的期望操作数。 n<1000,n-k<10,m<10000 Solution 考虑第i个物品的EGF为epimx−1e^{{p_i\over m}x}-1empix−1 枚举最后一个出现的物品为s，令Fs…

北大ACM——3046，Ant Counting（DP）

题意：有T种蚂蚁，总共A只，求将这些蚂蚁，分为数量为S,S1,S2,…,B的集合的总集合数。突破口： 设置a[T]记录每种蚂蚁的数量，设置dp[i,j]表示，用前i种蚂蚁，构成数量为j的集合的最大集合数…

【洛谷】 P1240 诸侯安置（递推）

洛谷P1240 诸侯安置点击此处去OJ 问题描述很久以前，有一个强大的帝国，它的国土成正方形状（需旋转45来看），图1所示为n3时的情况。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，因此国王准备给他们每…

北大ACM——2229，Sumsets（DP或思维）

题意：给定一个数N，要求出用2的次幂组成的等式的和等于N，输出有多少个符合条件的等式。如7，输出6： 11111111111121112211141222124 限制条件：1<N<1000000，结果对1e9取余。这道题可以dp来…

Codeforces 285E - Positions in Permutations 【题解待补全】

题目大意： 现在有一个1到n的排列p1,p2……pn 我们定义一个排位指数k k为数列中|pi-i|1的数量现在给你n和k，求n的排列中排位指数为k的排列的数量答案对10^97取模 1<n<1000 0<k<n 考虑前面i个数位置排位指数为j的情况这个时候考虑加…

[WC2018]州区划分

Description 给定一张n个点m条边的无向图，一个点的导出子图是不合法的当且仅当其不连通，或者存在欧拉回路。你现在需要把所有点划分成若干个点的导出子图，使得所有子图合法。每个点有点权wi，一个导出子图的价值定义为其之中的…

[CF 724E]Goods transportation

Description 给出n个点，第i个点原来有p[i]个“good”（我也不知道为什么要叫这个名字，看来是Chinese round吧），可以售出s[i]个“good”。对于两个点i,j(i < j)，你可以一次从i最多运送j个“good”到j&…

codeforces796E Exam Cheating

Zane and Zanes crush have just decided to date! However, the girl is having a problem with her Physics final exam, and needs your help. There are n questions, numbered from 1 to n. Question i comes before question i 1 (1 ≤ i < n). Each of the qu…

bzoj 1260: [CQOI2007]涂色paint

Description 假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆…

【DP】53.最大子数组和

题目法1：DP class Solution {public int maxSubArray(int[] nums) {if (nums null || nums.length 0) {return 0;}int n nums.length, res nums[0];int[] dp new int[n];dp[0] nums[0];for (int i 1; i < nums.length; i) {dp[i] Math.max(nums[i], d…

【力扣周赛】第 115 场双周赛（⭐优化背包DP）（TODO）

文章目录竞赛链接Q1：2899. 上一个遍历的整数💩（阅读理解题，按题意模拟）Q2：2900. 最长相邻不相等子序列 I（贪心）Q3：2901. 最长相邻不相等子序列 II（类似最长…

3417. 砝码称重（DP）【第十二届蓝桥杯省赛第一场C++A/B/研究生组】

3417. 砝码称重你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。请你计算一共可以称出多少种不同的正整数重量？ 注意砝码可以放在天平两边。输入格式输入的第一行包含一个整数 N。第二行包含 N 个整数：W1,W2,W3,⋅…

hdu 6103 Kirinriki dp+二分或尺取法

题目连接：hdu 6103 题意：找出整个字符串中两个相同长度，但不重叠的连续字串，求满足他们的距离小于等于m的最长长度。二分dp应该也是能写的，但是我错了，应该是dp没写好， 队友写的dp过了。 #i…

HDU_2602_背包问题

Description Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … The bone collector had a big bag with a volume of V ,and …

最长不上升序列（导弹拦截）（2种复杂度算法）

题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还…

CodeForces 316D3 PE Lesson

题意： N个人站在一条线上传球，每个人传球次数的上限为Ai（值为1或者2）,一开始每个人手上的球从左往右标为1..N，每一次传球，即是两个人手上的球互换，问传球后的所有的情况数（即最后产生…

$【区间DP】洛谷P1880石子合并题解$

【区间DP】洛谷P1880石子合并题解

【区间DP】洛谷P1880石子合并题解题目传送门分析典型的区间DP，我们可以建立状态f[i][j]表示将区间[i,j]内的石子合并的最大值。那么我们可以把[i,j]分为[i,k]和[k1,j](i<k<j)两个区间，分别合并后求出最大值。那么可以推出状态转移方程&…

[CF889E]Mod Mod Mod

Description 给出一个长度为n的序列a，定义f(x,n)x%a[n],f(x,i)x mod a[i]f(x mod a[i],i1) (1<i < n) 求最大的f(x,1) n<2*1e5,ai<1e13 Solution 我太菜了不会做，还是来翻译题解吧： 设x初始值mod a[1] mod a[2] mod a[3]……

51Nod 1050 循环数组最大字段和（ DP

循环数组最大子段和基准时间限制：1 秒空间限制：131072 KB 分值: 10 难度：2级算法题收藏关注 N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]a[i1]…a[j]的连续的子段和的最大值（循环序列是指n个数…

agc009e Eternal Average

Description 有n个0和m个1，每次操作选择k个数删去，并写上它们的平均数。求最后剩余的数有多少种可能。 n,m,k<2000 Solution 第一次的思路假了。。。。题意可以转化为有多少个数x可以表示成m个k^-i的和但为了保证合法我们需要保证1-x也可以…

2067. 走方格（DP）【第十一届蓝桥杯省赛第一场C++A/B组】

2067. 走方格在平面上有一些二维的点阵。这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。现在有个人站在第 1 行第 1 列，要走到第 n 行第…

[LeetCode] Predict the Winner 预测赢家

题目 Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the…

Vijos1243:生产产品（单调队列优化dp）

传送门题意： 有 n个任务，m 个机器，每个机器完成每个任务都有特定的时间，任务必须依次完成，且一个机器只能连续完成 l个任务，每次更换机器需要时间 k ，求完成所有任务的最短时间。 (n≤100000,m≤5)题解&#xff…

BZOJ1297: [SCOI2009]迷路（矩阵优化DP）

传送门题意： 给n个点的有向图，经过每条边需要不同时间，求从1点经过T时间到n点的不同方案数。(n<10,ti<9,T<1000000000)。题解： T很大，不能线性递推，n很小，发现每次递推式又一样，很容易想到…

BZOJ1009: [HNOI2008]GT考试(KMP+矩阵优化DP)

传送门题意： 给一个数串t，再给一个长度len,问长度为len的所有数串中有多少个不包含t(t不是它的子串)。题解： 设f[i][j]表示到第i位，前面已经匹配j位的数串的个数。对于一个状态f[i][j],可以转移到的状态有： 1 .f[i1][0]…

2018牛客多校第一场

E.Removal 题意：给一个长度为n的数字序列，每个数字大小都不超过k，要删除其中m个数字问有多少种删除后的序列不相同的方案。题解：DP。设dp[i][j]表示从1~i 删除j个数字的方案有多少种。首先初始化，很容易想到dp[i][0…

【题解】【DP】洛谷P1208尼克的任务

题目描述尼克每天上班之前都连接上英特网，接收他的上司发来的邮件，这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。尼克的一个工作日为N分钟，从第一分钟开始到第N分钟结束。当…

$【背包DP】洛谷P1060 开心的金明题解$

【背包DP】洛谷P1060 开心的金明题解

洛谷P1060 开心的金明题解题目传送门分析： 又是背包问题中大名鼎鼎的金明系列，与普通的背包不同，这道题有了“主件”和“附件”的概念但实际上我们并不需要单独考虑附件，只需要在对主件进行决策的时候同时考虑取附件的情况…

区间DP——石子合并

原题传送门代码 #include <bits/stdc.h> using namespace std; const int N310; int s[N]; int f[N][N]; int main() {int n;cin>>n;for(int i1;i<n;i) cin>>s[i];for(int i1;i<n;i) s[i]s[i-1]; //求前缀和for(int len2;len<n;len) //枚举每个区…

北大ACM——1742，Coins（多重背包）

多重背包问题。详解见博客： https://blog.csdn.net/Estia_/article/details/83590060 这道题时间卡得超严，在看大佬的代码之前疯狂TLE。代码如下： #include<cstdio> #include<iostream> #include<cstring> using names…

(java) leetcode 64.最小路径和

此题是一个很经典的动态规划题目了，思路不难，但是确实很体现动态规划的思想。然后我们就来分析一下这个题目。题目理解： 首先这是一个m*n的矩阵，我们需要寻找一条最短路径，从左上到右下，我们不能单纯考…

电脑接口: VGA、DVI、HDMI、DP

现状电脑显示器常见的接口主要有HDMI、DP、DVI、VGA等4种接口。显示器数据线性能排名：DP>HDMI>DVI>VGA。其中VGA是模拟信号，DVI、HDMI、DP 都是数字信号。 VGA接口 VGA(Video Graphics Array)是IBM在1987年随PS/2机一起推出的一种视频传输标…

编辑距离 51Nod - 1183

编辑距离 51Nod - 1183 编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符&…

最大连续子序列 HDU - 1231

最大连续子序列 HDU - 1231 给定K个整数的序列{ N1, N2, …, NK }，其任意连续子序列可表示为{ Ni, Ni1, …, Nj }，其中 1 < i < j < K。最大连续子序列是所有连续子序列中元素和最大的一个， 例如给定序列{ -2, 11, -4, 13, -5, -2…

NYOJ回文字符串

时间限制：3000 ms | 内存限制：65535 KB 难度：4 描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如”aba”。当然，我们给你的问题不会再简单到判断一个字符串是不…

浅谈动态规划DP

My thinking about dynamic programming 动态规划是一种以空间换时间的技巧，通常消耗的空间在接受范围内，但是速度却可以从指数级下降到多项式的时间。在学习动态规划之前，需要先了解： Overlapping SubproblemsOptimal Substr…

leetcode-70-dp经典算法题笔记

此题是一个经典的爬楼梯模型，是一个经典的使用dp去解决的问题之一。先介绍一个题目： 读完题目之后，我们也是先按照次序列举出来其他的几种情况： 当n1的时候，爬楼梯的方法是 1 所以共1种。当n2的时候，爬楼…

【LeetCode:70. 爬楼梯 | 递归 -＞记忆化搜索 -＞ DP】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，…

DP优化总结

矩阵优化DP例子fib数列fib数列拓展kmp转移小型图的转移决策单调栈优化例子玩具装箱Toy土地购买单调队列优化DP例子单调队列维护决策单调队列维护可选决策基环外向树的直径多重背包的OnmOnm优化斜率优化决策直线的斜率与二元组的横坐标同时满足单调性例题土地购买玩具装箱…

1214. 波动数列（DP）

1214. 波动数列题目链接观察这个数列： 1 3 0 2 -1 1 -2 … 这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有…

HDU动态规划入门练习题

DP是难点，供自已以后系统学习。 1.Robberies 连接 ：http://acm.hdu.edu.cn/showproblem.php?pid2955 背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱最脑残的是把总的概率以为是抢N家银行的概率之和… 把状…

插头 DP

垃圾插头DP，照着打都调了我一下午，淦！！！ 学这个玩意纯粹是因为模拟赛考了一道，要不然碰都不会碰…… 我觉得插头DP的主要难度在于实现，而不是理解算法原理…… 不说废话了，进入正…

擅长排列的小明 II NYOJ

时间限制：1000 ms | 内存限制：65535 KB 难度：3 描述小明十分聪明，而且十分擅长排列计算。有一天小明心血来潮想考考你，他给了你一个正整数n，序列1,2,3,4,5……n满足以下情况的排列： 1、第…

DP好题总结

LCIS最长公共上升子序列题解：https://blog.csdn.net/weixin_50624971/article/details/116892236 概括： 决策优化DP 考虑LCS可以写成 O ( n 4 ) O(n^4) O(n4) 的如果我们把状态设为 f [ i , j ] f[i,j] f[i,j] 表示考虑到 a [ i ] , b [ j ] a[i]…

【LeetCode】Sama的个人记录_25

【Q108】(md) 有序矩阵中第k小的元素给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。示例： matrix [ [ 1, 5, 9 …

AcWing1027. 方格取数

AcWing1027. 方格取数设有 NN 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。在走过…

【清华集训模拟】树

Description 给出一棵n个点的树，每个点有点权a[i] 求把这棵树划分成若干条不相交的路径，使得每条路径上的点权和均非负的方案数。 n<1e5 Solution 先考虑Dp怎么写，设Fx表示以x为根的子树已经覆盖完成了. 转移两条链，把这…

LeetCode70——Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 难度系数： 容易实现 int climbStairs(int n) {if (n < 2) {return n;} else {i…

积木

题目描述小A正在搭积木。有N个位置可以让小A使用，初始高度都为0。小A每次搭积木的时候，都会选定一个拥有相同高度的区间[A..B]，然后将位置[A1..B-1]上的所有积木的高度加一。不幸的是，小A把积木搭好之后没多久，小A调…

BZOJ 4260: Codechef REBXOR (01字典树+dp)

传送门：BZOJ 4260题目大意： 给你 n 个数，让你求两个不相交的区间元素异或后的和的最大值。本题中 n 的上限是 4*10^5.前置技能： 01字典树。思路： 首先看下异或的性质，关于异或我们知道： 0^aa ,…

BZOJ2199: [Usaco2011 Jan]奶牛议会（2-SAT+DP）

传送门题意： 2-SAT判定每个点是两种方案都可选还是只能选一种方案。题解： 明显，两种方案都可选只有两种方案之间没有可以到达的连边。可以每个点dfs一遍判断可行性，也可以缩点后在拓扑图上dp。如果dp时用bitset会更快。 #i…

【重点】【DP】300.最长递增子序列

题目法1：DP 必须掌握，O(N^2) O(N) class Solution {public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];Arrays.fill(dp, 1);int res 1;for (int i 1; i < nums.length; i) {for (int j 0; j < i; j) {if (nums[i] >…

$AtCoder Regular Contest 115 E. LEQ and NEQ（容斥单调栈优化dp）$

AtCoder Regular Contest 115 E. LEQ and NEQ（容斥单调栈优化dp）

题目 n(n<5e5)个数，第i个数ai(1<ai<1e9) 构造一个序列b，要求bi∈[1,ai]，且b[i]不等于b[i1] 求方案数，答案对998244353取模思路来源洛谷题解Xu_brezza 一模一样的cf题： Codeforces Round 759 (Div. 2…

SDAU训练日志第六篇----------动态规划（2）（2018年2月3日）

今天把老师给的课件看了一半多，看了几章C primer巩固基础，另外尝试看传说中《算法导论》结果看的有点懵逼。结合网上的一些资料有一些收获，感觉最大的收获就是搞懂了各种专业术语的含义还有分治法，贪心，动态规划之间…

leetcode-62-dp经典算法题笔记

然后开始分析一下，首先知道，这题肯定是dp思路的，虽然也能回溯，但是主要还是说dp，做个笔记。做dp题最重要的就是写出状态转移方程。我先举几个例子，从中寻找一下规律，因为dp思想规律都是差不…

鏖战字符串

题目描述 Abwad在nbc即将完成她的程序的时候，急中生智拔掉了她电脑的电源线，争取到了宝贵的时间。作为著名论文《论Ctrl-C与Ctrl-V在信息学竞赛中的应用》的作者，他巧妙地使用了这种上古秘术，顺利扳回一城。在决胜局中&#xf…

北大ACM——3616，Milking Time（DP）

突破口：只要发现DP对象是间歇M，便可发现本质是最大递增子序列。代码如下： #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long dp[1005]; struct mt {i…

bzoj 4247: 挂饰

Description JOI君有N个装在手机上的挂饰，编号为1...N。 JOI君可以将其中的一些装在手机上。JOI君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有…

【GDOI2016模拟4.23】无界单词

Description 学过kmp吗？ 一个只由a和b组成的字符串S，如果next[|S|]0，那么这个单词就是无界的，否则就是有界的。给出n和k，求长度为n的无界单词有多少个，和其中字典序第k小的是什么。多组询问。 Type&…

Codeforces Round #260 (Div. 1) A.Boredom

今天是下定决心好好练DP的第一天，从1600的DP开始做起。题目链接：点击打开原题目。题意：给一个长度位n的整数序列，每次选择一个数字删除，删除这个数的同时比这个数大1和小1的数全部被删掉，每次得到的值就…

【GDKOI2017模拟1.12】与运算

Description 给出一个序列，Fi为前i项进行and运算之后的值。求这个序列的一个排列，使得∑Fi最大。输出这个最大值。 n<10^6 Solution 首先考虑F数组，显然是单调不升的。那么我们考虑Dp，Dp i表示F数组目前最后一位为i的最…

Ural1776： Anniversary Firework（概率DP）

传送门题意： n个火箭排成一排一开始点燃第一个和最后一个火箭然后每次只能在点燃过的火箭中的火箭每两次点燃火箭的间隔时间为10s求点燃n个火箭等待时间的期望题解： 我还是太Naive了，一开始以为是期望区间DP，dp[i]表…

String painter

题意： 给出两个串s1和s2，一次只能将一个区间刷一次，问最少几次能让s1s2 例如zzzzzfzzzzz，长度为11，我们就将下标看做0~10 先将0~10刷一次，变成aaaaaaaaaaa 1~9刷一次，abbbbbbbbba 2~8:abccccccc…

SGU315：The Highway Belt（DP）

传送门（Vjudge） 题意： 给n条线段，用这些线段中的一些围成一个围绕原点的多边形，满足原点发出任意射线与此多边形只有一个交点。求满足条件的多边形的最大周长。(n≤50)题解： 写了一种O(n6)的DP,但是上界…

杭电ACM——fatmouse's speed（DP）

最长递增子序列（与最大递增子序列基本一样） 状态：dp[i]：前i个数当中，以a[i]为结尾的递增子序列的最大长度状态转移方程跟之前写的那篇最大递增子序列的差不多 #include<cstdio> #include<algorithm> #in…

百团大战

题目描述此百团大战非彼百团大战也。这指的是HYSBZ的社团开始招人了。若若的LMZ现在站在操场上，有很多很多个社团在操场上排成一排。有些社团为了吸引人们加入，会表演节目。而现在LMZ拿到了节目单，有n个节目，其描述了在Ti时刻Xi…

杭电ACM——1003，Max Sum（DP）

突破口：把握好sum<0的意义 #include<cstdio> #include<iostream> using namespace std; int a[100005]; int main() {int T,n,i,kase;int max,sum,start,end,st,et; //max作为最终输出的答案，sum作为游标，去探测scanf(&quo…

UVa 10529 : Dumb Bones（期望DP）

传送门题意： 你试图把一些多米诺骨牌排成直线，然后推倒它们。但是如果你在放骨牌的时候不小心把刚放的骨牌碰倒了，它就会把相临的一串骨牌全都碰倒，而你的工作也被部分的破坏了。比如你已经把骨牌摆成了DD__DxDDD_D的形状&…

[51nod1450]闯关游戏

Description 有n个游戏，互相独立，对于第i个游戏，每次玩有1-xi-yi的概率失败，xi的概率获得一颗星，yi的概率获得两颗星。对于每个游戏我们会记录你的历史最好成绩。对于所有游戏，通关的条件为：…

HDU - 4784 Dinner Coming Soon （DP+BFS）

Coach Pang loves his boyfriend Uncle Yang very much. Today is Uncle Yang’s birthday, Coach Pang wants to have a romantic candlelit dinner at Uncle Yang’s house and he has to arrive there in T minutes. 　　There are N houses in their city numbered from 1 …

HDU - 5459 Jesus Is Here （DP）

Ive sent Fang Fang around 201314 text messages in almost 5 years. Why cant she make sense of what I mean? But Jesus is here!" the priest intoned. Show me your messages." Fine, the first message is s1‘‘c" and the second one is s2‘‘ff&quo…

【3.16XJ模拟题】圆

Description 二维坐标平面内有n个圆，第i个圆圆心在(Xi,Yi)，半径为Ri，权值Vi。任何两个圆都不会相交（也不会相切），但是圆与圆之间可能存在包含关系。当我们在一个圆里面的时候，我们必须经过它的…

[51nod1169]石子游戏

Description 有n堆石子，第i堆有ai个。现在要从这n堆石子的任意堆中拿走任意个石子，使得如果两个人用这n堆石子玩nim游戏先手必败。但要求至少有一堆石子不动。求方案数对1e97取模之后的结果。 n<100,ai<1e9 Solution 显然我们只需要异或…

hdu 6170 Two strings dp模拟

Problem Description Giving two strings and you should judge if they are matched.The first string contains lowercase letters and uppercase letters.The second string contains lowercase letters, uppercase letters, and special symbols: “.” and “”.. can ma…

【NOIP2015模拟11.2晚】舳舻牌

Description Alice和Bob，哦不，CZL和YYY在玩一个游戏。桌上有n张牌，每张牌对两人各有一个诱惑值，和它自己的价值。CZL先手，每次操作方喊出一个值X，然后把桌上剩下的对他诱惑值<X的牌全部收走&#xff08…

BZOJ3572: [Hnoi2014]世界树（虚树）

传送门题意: 一棵树，每次给k个控制点，求每个控制点能控制几个点。（一个点被离它最近的控制点控制）。题解： 虚树。首先建出虚树，考虑怎么dp。首先要dp出离每个虚树上的点最近的点。 dp两次即可。…

acwing 1055. 股票买卖 II

题面题解(状态机模型) f[i][0] : 第 i 天手中没有股票 f[i][1] : 第 i 天手中有股票 f[0][0] 0 （第0天手中没有股票）f[0][1] -INF(非法状态，题中让求最大值，所以初始化为最小值) 代码 #include<iostream> #include<cst…

力扣打家劫舍 II

题面题解(状态机模型) 对于线性 f[i][0] max(f[i-1][0],f[i-1][1]) ; f[i][1]f[i-1][0]w[i] ,对于环形，我们可以用枚举的方法，我们假设第一个点不选，那么f[0][0] 0,f[0][1]-INF(不合法) ，最后的最大值就是max(f[n-1][0],f[n-1]…

洛谷 p1803（dp做法）

为了练习dp，当成dp做的地址：https://www.luogu.org/problemnew/show/P1803 首先dp[i]表示在前几场比赛时间中可以选几场那么转移方程就是dp[i]max(dp[i-1],dp[temp]1) 前者是不选第i场，后者是选第i场而dp[temp]表示从dp[i-1]向前找到第一…

NYOJ石子合并（一）

石子合并（一） 时间限制：1000 ms | 内存限制：65535 KB 难度：3 描述有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合…

背包小专题

背包小专题 1. CF106C Buns题目描述题目概况思路点拨代码实现 2. CF864E Fire题目描述题目概况思路点拨代码实现 3. CF366C Dima and Salad题目描述题目概况思路点拨背包瓶颈解决方法代码实现 4. CF1132E Knapsack题目描述题目概况思路点拨代码实现 5. CF632E Thief in a Shop…

【DP】70.爬楼梯

题目法1：dp 相当于计算斐波那契数列 class Solution {public int climbStairs(int n) {if (n 1) {return 1;}if (n 2) {return 2;}int pre0 1, pre1 2, res 0;while (n - 2 > 0) {res pre0 pre1;pre0 pre1;pre1 res;--n;}return res;} }

codeforces 914C. Travelling Salesman and Special Numbers （DP + 组合数学）

传送门：codeforces 914C 题目大意： 定义一种 reduce操作为将一个数用其二进制下 1 的个数代替。给定一个二进制数 n，问小于等于 n的数中，需要进行 k次 reduce操作才能变为 1的数有多少个？ 例如：7 -> 3…

【1096】[ZJOI2007]仓库建设

Description L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天&am…

【WC2016模拟】计数系统(stones)

Description n,k<2000,T<50 Solution 是不是很容易想到数位Dp？ 讲一下我考场上想到的辣鸡做法，从中间向两边对称着做，满足第三个条件必然在某个时刻出现左端点为0，右端点为1，分成两段Dp。特别难写而且自带一…

【WC2016模拟】计数系统(stones)

Description n,k<2000,T<50 Solution 是不是很容易想到数位Dp？ 讲一下我考场上想到的辣鸡做法，从中间向两边对称着做，满足第三个条件必然在某个时刻出现左端点为0，右端点为1，分成两段Dp。特别难写而且自带一…

51nod 1052 最大m子段和 DP

转载自：http://blog.csdn.net/winter2121/article/details/72848482 最大m子段和一、定义给定由n个整数（可能为负）组成的序列a1、a2、a3...,an, 以及一个正整数m，要求确定序列的m个不想交子段，使这m个子段的总和最大…

acwing 896 最长上升子序列II （二分单调优化）

题面题解对于未优化的最长上升子序列问题，我们用 f[i] 来表示以 i 结尾的最长上升子序列 ，然后枚举 i 前面的数，来更新 f[i] 。这样是 O(n2) 的，此题数据范围大，会超时优化版其实是贪心的思想，对于长度…

算法竞赛进阶指南---0x12 最大子序和

题面题解这其实是一道单调队列优化区间dp问题，对于这个序列，我们可以划分为n个区间，每个区间代表以ai结尾，长度不超过m的子序列和，我们只需要遍历一遍每个集合，找到每一个集合中的最大值，那么…

POJ1259：The Picnic（DP）

传送门题意： 给n个点，求最大凸多边形，要求内部没有点(n≤100)。题解：DP 预处理两两到原点的三角形中包含的点的个数以便O(1)查询任意三角形中包含的点（我写的代码边界十分繁琐，不知道哪位dalao看了能教教我怎么写得简便一…

【DP】64.最小路径和

题目法1：二维DP 必须掌握！ class Solution {public int minPathSum(int[][] grid) {int m grid.length, n grid[0].length;int[][] matrix new int[m][n];matrix[0][0] grid[0][0];for (int i 1; i < n; i) {matrix[0][i] matrix[0][i - 1]…

带权的活动安排问题-利益最大化-DP

基础的贪心问题-活动安排问题是这种问题的特殊情况（权值为1）。但这个问题不能用贪心算法而是应该用动态规划算法来求解。这种问题下的另一种较特殊情况是每段任务的权值是它的时间长度，使活动安排时间最满，同样要用到动态规划算法…

【DP】62.不同路径

题目法1：二维DP 必须掌握！ class Solution {public int uniquePaths(int m, int n) {int[][] matrix new int[m][n];Arrays.fill(matrix[0], 1);for (int i 0; i < m; i) {matrix[i][0] 1;}for (int i 1; i < m; i) {for (int j 1; j <…

2016多校训练Contest6: 1002 A Simple Chess hdu5794

Problem DescriptionThere is a nmboard, a chess want to go to the position (n,m)from the position (1,1).The chess is able to go to position (x2,y2)from the position (x1,y1), only and if only x1,y1,x2,y2is satisfied that (x2−x1)2(y2−y1)25, x2>x1, y2>…

【重点】【DP】300. 最长递增子序列

题目更好的方法是耐心排序，参见《算法小抄》的内容！！！ 法1：DP 基础解法必须掌握！！！ class Solution {public int lengthOfLIS(int[] nums) {if (nums null || nums.length 0) …

河工大校赛最大子段和

1266: 最大子段和时间限制: 1 秒内存限制: 64 MB 提交: 395 解决: 99 提交状态题目描述一个大小为n的数组a1到an(−10^4≤ai≤10^4)。请你找出一个连续子段，使子段长度为奇数，且子段和最大。输入第一行为T(1≤T≤5),代表数据组数。之后每…

bzoj 1911: [Apio2010]特别行动队

Description Input Output Sample Input 4 -1 10 -20 2 2 3 4 Sample Output 9HINT 斜率优化DP 首先我们考虑初始转移方程f[i]max(f[j]a*(s[i]-s[j])^2b*(s[i]-s[j])c);其中s为x的前缀和考虑j>k的时候j比k优那么有f[j]a*(s[i]-s[j])^2b*(s[i]-s[j])c<f[k]a*(s[i]-s[k…

【WC2016模拟】几何

Description n<60000,T<5 时限0.8S Solution 忽略掉题面最开始三个字显然这题分为两部分第一部分是求出Dp[i]表示i-多面体的选择方案数。第二部分是把Dp[1]~Dp[n]组合起来。第二部分显然可以用分治FFT来搞（求n个一次多项式的乘积）&…

GDOI 2016 Day1 T2 最长公共子串

Description 给出两个字符串A和B，求最长公共子串。其中B串中有k个区间的字符可以任意调换。 |A|,|B|<2000,k<100000 Solution 首先，一个很明显的性质，两个区间如果有交集，那么这两个区间可以合并成一个。然后&#…

杭电ACM——2069，Coin Change（DP）

看了这位大佬的博客： https://blog.csdn.net/qq_41636123/article/details/82469396 发现，原来这是一道二维费用的背包问题。设置三维数组dp[i,j,k]： 状态：dp[i,j,k]表示用前i种硬币，硬币用了j个，总面值为…

杭电ACM——1087，Super Jumping! Jumping! Jumping!（DP）

最大递增子序列问题状态：dp[i]:前i个数当中，以a[i]为结尾所能构成的最大递增子序列的各数字之和； 状态转移方程在代码中解释 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define…

bzoj 4720: [Noip2016]换教室

Description 对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。在可以选择的课程中,有2n节课程安排在n个时间段上。在第i(1≤i≤n)个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室ci上课,而另一节课程在教室di进行。…

【GDOI2017模拟8.11】选择

之前漏了一天的blog，补上。 Description 有n中物品，每种物品有无限个，第i种物品的单价为ai。问从中选出k个物品的价格有多少种，以及这些钱数。 n,k,ai<500 Solution 首先，可以有一个很显然的DP模型。设F[i…

杭电ACM——毛毛虫（DP）

状态：dp[k,i]：k分钟后，毛毛虫爬到第i个位置的方案数状态转移方程： dp[k,i] { dp[k-1,i-1] in; dp[k-1,i1] i1; dp[k-1,i-1]dp[k-1,i1] } 边界处理： iPk||Pik,dp[k,i]1; else dp[k,i]0; 代码如下； #inclu…

动态规划汇总

1.概率/期望dp 一般题目中很明显会涉及到概率的字样，常用的方法有高斯消元...... 这是道十分有趣的结合了字符串的概率dp，要通过定义的方式转换为期望dp计算 P6125 [JSOI2009]有趣的游戏这道是上一个的加强版，需要重新考虑dp的方式来减少…

【NOIP2017提高A组集训10.22】友谊

Description 一个长度为2m的序列，每个位置可以是0或1 任意两个i < j，i为偶数，j为奇数的0/1相同的位置可以匹配，每个位置最多匹配一次求有多少个序列满足匹配完剩余的位置<2n 答案对p取模 n,m<3000,p<1e97 Solu…

bzoj 1096: [ZJOI2007]仓库建设

Description L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天&…

2016多校训练Contest4: 1001 Another Meaning hdu5763

Problem DescriptionAs is known to all, in many cases, a word has two meanings. Such as “hehe”, which not only means “hehe”, but also means “excuse me”. Today, ?? is chating with MeiZi online, MeiZi sends a sentence A to ??. ?? is so smart that …

$2019牛客暑期多校训练营（第五场）G subsequence 1（DP+组合数学）$

2019牛客暑期多校训练营（第五场）G subsequence 1（DP+组合数学）

链接：https://ac.nowcoder.com/acm/contest/885/G 题意：T组样例，每组样例第一行给出n、m，表示字符串s的长度和字符串t的长度。接下来两行分别给出s和t。s和t都由阿拉伯数字组成。保证n>m,并且他们的第一个字符都不是0。问s中有…

Cheapest Palindrome（POJ-3280）

题意：给一个长度为m的字符串s，其中含有n种字母，给出添加和删除某种字母所需要的代价，你可以通过添加或删除某些字母来使这个字符串变成回文串，求使当前这个字符串变成回文串需要的最少代价是多少。题解：典…

【GDOI2014模拟】服务器

Description 我们可以从n个数中选择一些，选择第i个数的代价为Ci，且必须选择n。对于每个没有被选择的数i，若它右边离它最近的一个被选择的数是j，则代价为j-i。求最小代价。 n<10^6 Solution N^2Dp还是很显然的。设Fi表示…

Non Absorbing DFA DP (ASC2A SGU201 ZOJ2337 ACdream1218 Gym100197A)

SGU 201 Non Absorbing DFA DP ( ZOJ 2337 、ACdream 1218 、Gym 100197A) Andrew Stankevich Contest 2 A题题意给定一个DFA（有字符集、初始状态、终态集，每个状态遇到每个字母会转换到哪个状态）。问某个长度的字符串有多少种可以被该…

牛客小白月赛34 C dd爱科学2.0

题面题解 f [i] [j] : 已经处理到了前 i 个字母，第 i 个字母是 j 的最小花费因为这个序列是非递减的，所以前一个不能大于后一个，直接枚举第 i -1 个字母是什么，来转移方程,最小花费就是 s[i] 变到字母 j‘A’ 的偏移量代码 #…

codeforces 1529 D.Kavi on Pairing Duty

题面题意给你一个n，坐标上有2n个点，间距为1，让你求出满足题意得方案数。每两个点连接成一条线段，要求线段两两之间要么长度相等，要么一个线段被另一个线段包含题解(找规律) 设ai表示，ni 时有多少方案数…

$C++ 【NOIP2011】计算系数——利用另类DP巧解$

C++ 【NOIP2011】计算系数——利用另类DP巧解

题目描述给定一个多项式(ax by)^k，请求出多项式展开后x^n y^m项的系数。输入输入文件名为 factor.in。共一行，包含 5 个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开…

石油大 Contest1777 - 2019年第二阶段我要变强个人训练赛第九场 J 流浪西邮之寻找火石碎片（背包）

时间限制: 1 Sec 内存限制: 128 MB 提交: 81 解决: 28 [提交] [状态] [命题人:admin] 题目描述众所周知，由于木星引力的影响，世界各地的推进发动机都需要进行重启。现在你接到紧急任务，要去收集火石碎片，重启西邮发动机。现在…

LeetCode 1289. 下降路径最小和 II：通俗易懂地讲解O(n^2) + O(1)的做法

【LetMeFly】1289.下降路径最小和 II：通俗易懂地讲解O(n^2) O(1)的做法力扣题目链接：https://leetcode.cn/problems/minimum-falling-path-sum-ii/ 给你一个 n x n 整数矩阵 arr ，请你返回非零偏移下降路径数字和的最小值。非零偏移下…

BZOJ1023: [SHOI2008]cactus仙人掌图（单调队列优化DP）

传送门题意: 求一颗仙人掌的直径。题解： DP。首先建出图的DFS树。因为是仙人掌图，所以每个环必定有一个dfs序最小的点，连接着若干条后向边和树边，表示环上的边或者割边。记录f[i]表示dfs树上以i为根的子树（子图）中最…

5408. 保险箱

5408. 保险箱 - AcWing题库 #include <iostream> #include <string> #include <algorithm> #include <cstring> using namespace std;const int N 1e5 10; string x, y; int f[N][3], n; int main() {cin >> n >> x >> y;memset(…

Java实现藏宝架的宝物（分组DP,7.27阿里面试题）

有个藏宝架有n层，每层的宝物数量不一，每个宝物都有其价值，现在要求拿出m个宝物，并且需要遵守规则： 每次只能拿选定层的两端的宝物要拿出的m个宝物的总价值是各种方案里最大的输入： n是层数，m是…

TextView的setTextSize与xml中android:textSize属性值的对应关系

android中，对TextView设置文本字体大小，是通过在layout xml中设置android:textSize的属性值实现的，比如设置“24sp”，这里的sp是一种单位，其他可选的单位还有px，dip(dp)，pt，in&#…

【达内课程】dp转px和屏幕适配

【达内课程】自定义控件（文字阴影）中设置了文字大小为48，这里的48是px，也就是像素，而我们平时设置大小用的是dp 现在在布局上放置一个TextView，设置TextSize为48dp，我们观察下效果看一下dp和…

杭电ACM——天上掉馅饼（DP）

注意点： time1：活动范围为4-6； time2：3-7； time3：2-8； time4：1-9； time5：0-10（全范围） 突破口： 状态：dp[i,j]在…

Wannafly挑战赛12 C删除子串

链接思路：a,b数组存放到达变化数j所需要的最大长度，对于每次能够到达的变化数j，一定是由b[j-1]或a[j]的状态到达，加上当前字符的长度1，同理b数组也有相应的达到过程。 { a[j]max(a[j]1, b[j-1]1);b[j]max(b[j]1,a[j-1…

ds套dp——考虑位置转移or值域转移：CF1762F

https://www.luogu.com.cn/problem/CF1762F 分析性质，就是我们选的数要么递增，要么递减（非严格）然后很明细是ds套dp， f i f_i fi 表示以 i i i 开头的答案然后考虑如何转移（ds套dp难点反而在转移而不是…

FZU 2214 Knapsack problem （超大01背包）

传送门：FZU 2214题目大意： 有 n 种物品，每种物品有重量 w[i] 和价值 v[i]，从中选出几件物品，求重量不超过 B 时的最大价值。注意，物品的重量很大（w[i]<10e9）。思路： …

647. Palindromic Substrings

647. Palindromic Substrings Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. 算法思路…

北大ACM——2385，Apple Catching（DP）

dp[T,W,N]: 在T分钟，移动次数剩余W次时，在第N棵树下可以拿到的苹果的最大数量。简化： 一开始因为奶牛是在第一棵树，而苹果树只有两棵，因此奶牛的位置可以由剩余移动次数W来确定，故 dp[T,W,N] → dp[T,W]: …

leetcode-05-dp经典算法题笔记

题目概述： 首先我们看见这个题的目的，是要找到一个字符串中的最长回文子字符串，换句话说，正着倒着都一样。思路： 最简单的办法，就是n穷举，但是这是不行的肯定，所以我们也是采用动…

【算法】矩阵快速幂优化动态规划

文章目录知识讲解题目列表[矩阵快速幂] 题目列表📕70. 爬楼梯解法1——线性DP解法2——矩阵快速幂 509. 斐波那契数1137. 第 N 个泰波那契数1220. 统计元音字母序列的数目解法1——线性DP解法2——矩阵快速幂优化DP 552. 学生出勤记录 II（🚹…

2023年第六届传智杯程序设计挑战赛（个人赛）B组赛后复盘

传智杯赛后复盘大家好我是寸铁👊 2023年第六届传智杯程序设计挑战赛（个人赛）B组赛后复盘喜欢的小伙伴可以点点关注 💝 1. 字符串拼接细节：一定要清楚nextLine()和next()的区别 nextLine()是遇到回车会停下来 nex…

codeforces D. Array Collapse

DP一生之敌 learn from AC-Panda and codeforces’s Tutorial 思路 d p [ i ] dp[i] dp[i] 表示以 a [ i ] a[i] a[i] 结尾的方案数， s u m [ i ] sum[i] sum[i] 表示 ∑ j 1 i d p j \sum\limits_{j1}^idp_j j1∑idpj 。对于 d p [ i ] dp[i] dp[i] 当 …

[AGC022F]Checkers

Description 令x10100x10^{100}x10100，数轴上有n个点，第i个点的坐标为xix^ixi 进行n-1次操作，第i次操作选择两个点A和B，将A变为A关于B的对称点，然后删去B 最后会剩下1一个数，问这个数有多少种可能的取值 n…

[AGC027E]ABBreviate

Description 给出一个字符串s，每次操作可以选择子串aa变为b，也可以选择子串bb变为a 问能得到的本质不同的字符串数量 |s|<10^5 Solution xjb编了7788还是去看题解了_(:з」∠)_ 首先，一个字符串能变成一个字符a或b，需要存在…

[CF506E]Mr. Kitayuta's Gift

Description 给出一个字符串s，你需要往其中插入n个小写字符得到字符串t，使得t是一个回文串问所有能得到的本质不同的t的个数 |s|<200,n<10^9 Solution 先考虑最暴力的做法，我们设F[l][r][k]表示当前s[l…r]还没有被匹配&#xff0c…

带限制的无标号树计数

前言我又来学数树了最近化学老师教我们手把手写烷烃同分异构体然后我又想到了这个远古老题 Dp 首先我们计有根树，假设度数限制为m 设Fi,jF_i{,_j}Fi,j表示i个点，根节点子树大小为j的树的个数设Ai∑j0m−1Fi,jAi\sum_{j0}^{m-1}F_{i,j}Ai∑j0m…

[CodeChef Nov Challenge]Max-digit Tree

Description 给出以1为根的有根树，每个点上有个数字di (d1!0) 定义一个包含1的连通块对应的数是其按编号从小到大做dfs序得到的序列中，di按顺序连接起来形成的数字定义序列a，满足a11,aiai−1maxdigit(ai−1)a_11,a_ia_{i-1}maxdigit(a_{i-1…

[LOJ6395]「THUPC2018」城市地铁规划 / City

Description 定义一棵树的价值为∑f(deg(i)) 其中f为一个给定的函数构造一棵树使得价值最大。 n<3000 Solution 比赛的时候xdl写了一个n^2log n基于调和级数的做法。现在想想当时真的是被降智了~~ 直接设背包显然是不行的，因为我们强制要选n个物品但…

Marvell交换机QoS命令调试记录

3.16.1 QoS default-up 语法： qos default-up {0-7} 参数说明： 0-7 —— 允许的UP值范围命令模式： Interface(Ethernet, Port-channel)configuration mode 应用举例： Console# configure Console(config)# interface ethernet 0/0 Console(config-if)# qos defaul…

【NOIP2017提高A组模拟9.7】简单无向图

Description 给出一张n个点的简单图，和每个点的度数di，求这样的图的个数。 n<2000,di1,2 Solution 既然度数只有1,2两种，那么显然这种图中只有环和链。但是这个环有要求大小>3，因为简单图不能有重边。很好想到把环和…

孤独一生

题目描述下课了，Polo来到球场，但他到了之后才发现…..被放了飞机…… 无事可做的他决心找点乐子，比方说……跳台阶…… 球场边有N个台阶拍成一行，第i个台阶的高度是Hi(Hi<10^9)，第0个台阶，也就是地面的…

[51nod 1306]高楼和棋子

Description 一栋高度为n层的楼，你有m个棋子，在第x层以上扔棋子会碎。问对于x0~n，最坏情况下需要试多少次才可以试出这个x。 T<50000,1 < N < 10^18, 1 < M < 64 Solution 是不是长得有点眼熟？ 相信大家都在…

华为机试：学生方阵

【编程题目 |200分】学生方阵【2022 Q2 考试题】题目描述学校组织活动，将学生排成一个矩形方阵。请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上，方向可以是水平的，垂直的，成对角线的或者呈反对角线的…

博弈论（奇偶考虑法）+计数+DP（判定转dp）：CF838C

首先题目有博弈，先分析一波最优策略（步骤：分析性质）。两个人，所以显然考虑奇偶考虑法递归考虑。首先删就是使子问题-1，重新排列是在当前子问题里的。一个串的排列是有限的，所以这里就可以…

[51nod1201]整数划分

Description 求将一个正整数n划分成不同的正整数的和的方案数。 n<50000 Solution 很巧妙的一道DP题。我们设Fi,j表示将i划分成j个不同整数的方案。 j的上界大概是根号n的，不会超时。那么我们有两种转移方案。我们可以从Fi-j,j转移过来，把…

bzoj 3233: [Ahoi2013]找硬币

Description 小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1，xb必须为xa的正整数倍（b>a）。例如 1，5，125，250就是一组合法的硬币序列&#xff0c…

bzoj 4831: [Lydsy2017年4月月赛]序列操作

Description 给定一个长度为 n 的非负整数序列 a_1,a_2,...a_n 。你可以使用一种操作：选择在序列中连续的两个正整数，并使它们分别减一。当你不能继续操作时游戏结束，而你的得分等于你使用的操作次数。你的任务是计算可能的最小得分和最大得分…

【NOIP2013模拟联考5】军训(training)

Description 给出一个序列，序列的每个位置有两个值，H和G。现在要把这个序列分成几份。每一段必须是连续的，并且要求每一段的max(Hi)的和<lim,且使每一段的∑Gi的最大值最小。求这个值。 n<20000 Solution 看到双最值&#xff0…

【算法】背包问题——01背包

题目有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数&#xff0…

贪心+二分+DP+矩阵快速幂：CF461E

https://codeforces.com/contest/461/problem/E 第一步：捕捉题目信息四种字符 → \to → 矩阵 n ≤ 1 0 18 → n\le 10^{18}\to n≤1018→ 矩阵快速幂 → \to → dp最小值最大 → \to → 二分第二步：分析性质 s s s 未知？那如果已知怎…

洛谷P1736 创意吃鱼法（DP）

题意大概就是要从一个n * m的矩阵当中，求出一个主对角线或者副对角线都是1，其它地方都是0的最大正方形，并输出它的边长。最暴力的方法应该就是枚举，对于任何一点(i , j)，枚举它作为正方形的左上顶点/右上顶点时&#…

bzoj 3437: 小P的牧场

Description 背景小P是个特么喜欢玩MC的孩纸。。。描述小P在MC里有n个牧场，自西向东呈一字形排列（自西向东用1…n编号），于是他就烦恼了：为了控制这n个牧场，他需要在某些牧场上面建立控制站，每…

51nod 1202 子序列个数（DP）图解

传送门：51nod 1202 思路： 设 dp[ i ] 表示前 i 个字符可以形成的非重复子序列个数。当第 i 个字符在之前未出现过时，有 dp[ i ] dp[ i-1 ] * 2 1 ；即前 i-1 个字符可以形成的子序列数将第 i 个字符加到前 i-1 个字符形成的子…

牛客25147，金币馅饼（DP）

要从(1,1)走到(R,C)，根据走的方式，可以定义以下的状态和方程。状态：dp[i,j]表示走到(i,j)位置时能够获得的最大金币数状态转移方程： if(i!j) dp[i,j]max(dp[i-1,j-1],dp[i,j-1],dp[i1,j-1])map[i,j] else dp[i,j]dp[i-1,j-1]map…

2019牛客暑期多校训练营（第四场）K

可以用DP来做，可参考博客： https://www.cnblogs.com/Yinku/p/11256242.html 状态：dp[k,i]表示以s[i]为结尾，前缀和mod3k的子串个数； 边界：dp[0~2,0]0，dp[s[i]%3,0]; 状态转移： 设s[i…

《背包九讲》学习笔记（未完待续）

《背包九讲》学习笔记（未完待续） 背包九讲下载地址 1. 01 背包问题描述 n个物品放进容量为v的背包，第i个物品的价值为wi，花费为ci，问能装入物品的最大总价值。核心代码 ///dp[j]为前i个物品装在容量为j的背包内可…

bzoj 3622: 已经没有什么好害怕的了

Description Input Output Sample Input 4 2 5 35 15 45 40 20 10 30 Sample Output 4HINT 学姐走好_(:з」∠)_ 容斥DP f[i][j]表示前i个有j对大于药片。剩下i-j对情况随意的种数 f[i][j]f[i-1][j]f[i-1][j-1]*(next[i]-j1 然后去除重复的然后f[n][k]就是答案了#include<c…

状压dp：Gym - 102832J

https://vjudge.net/contest/587311#problem/G 认真读题，然后发现就是让区间不交，要么包含要么相离，长度为偶数，直接状压状压就状压10位就行。转移发现长度为偶数，所以可能填法只有 2 5 2^5 25。总复杂度 O ( n 2…

杭电ACM——2546，饭卡（DP）

一维背包问题。突破口：将菜的价格从小到大排序，对前n-1个物品进行DP，找出消费金额不超过m-5的方案中最大的消费金额sum，在此基础上，m - (sumprice[n]) 即为卡内最小余额。因此，我们DP应在余额为0~m-5之内…

洛谷 2511 [HAOI2008]木棍分割

题意：如题思路：首先二分枚举最大的长度。 dp[i][j]表示前一个木棍，切了j刀符合条件的方案数。 dp[i][j]dp[k][j-1] (sum[i]-sum[k]<ans) 这个转移可以用前缀和维护。状态总共O(n*m)，转移O（1） #inclu…

CF1110 D. Destroy the Colony (DP)

题意：给你一串数字，问你最多有多少个[x,x1,x2]或者[x,x,x]这样的思路： 用DP[i][j][k]表示有j个[x-1,x,x1],还有k个[x,x1,x2]的最多三元组。 dp[i][k][l] max(dp[i][k][l], dp[i - 1][j][k] (Sum[i] - j - k - l)/3 l) ; 一开始先加上…

牛客网哈尔滨工程大学第十四届程序设计竞赛（同步赛）——D 简单的烦恼（DP）

这道题可以用DP来做，实质上是个背包模型，因为它有一个费用t。状态：dp[i,j]表示前i首歌，在j分钟内可以听的歌曲的总时长。状态转移方程： dp[i,j] if(j<song[i]) dp[i-1,j]; else max(dp[i-1,j],dp[i-1,j-song[i]]s…

杭电ACM——humble numbers（DP）

突破口：状态是线性的，只需一维数组dp[n]。dp[i]表示第i个humble number，humble numbers是递增序列，因此dp[i]>dp[i-1]，且是第一个大于dp[i-1]的，dp[i]一定是由前面某个数乘上2,3,5或7得到的。先用2去乘d…

用树形dp+状压维护树上操作的计数问题：0902T3

发现操作数 k ≤ 6 k\le6 k≤6，可以考虑对操作进行状压。然后找找性质，发现要么删掉一棵子树，要么进去该子树。可以视为每种操作有两种情况。然后分讨一下当前该如何转移。树形dp的顺序： 合并子树考虑当前往上的边的方向 …

【DP】121.买卖股票的最佳时机

题目法1：DP 简单题目 class Solution {public int maxProfit(int[] prices) {if (prices.length 1) {return 0;}int min prices[0], profit 0;for (int i 1; i < prices.length; i) {min Math.min(min, prices[i - 1]);profit Math.max(profit, prices…

[蓝桥杯 2014 省 A] 波动数列

题目链接 [蓝桥杯 2014 省 A] 波动数列题目描述观察这个数列： 1 3 0 2 − 1 1 − 2 … 1\ 3\ 0\ 2\ -1\ 1\ -2\ … 1 3 0 2 −1 1 −2 … 这个数列中后一项总是比前一项增加 2 2 2 或者减少 3 3 3，且每一项都为整数。栋栋对这种数列很好奇&#…

【上分日记】377场周赛(图论 + dp)

文章目录前言正文1.2975. 移除栅栏得到的正方形田地的最大面积2.2976. 转换字符串的最小成本 I3.2977. 转换字符串的最小成本 II 总结后文前言本场周赛，后两题都涉及到了图论的最短路径（克鲁斯卡尔算法）的知识，恰巧又没学过&am…

Project Euler 865 Triplicate Numbers（线性dp）

题目能通过每次消除3个一样的数字，最终把数字消成空的数字是合法的， 求串长度不超过n的，没有前导0的数字中，合法的数字的个数 n10000，答案对998244353取模，只需要输出数字思路来源乱搞AC 题解暴力…

【WC模拟】优美的树

Description 众所周知，树是n 个节点n-1 条边的结构，而所谓的优美的树需要满足如下条件： 1. 这是一棵有根二叉树； 2. 非叶节点需有两个儿子； 3. 不可以变换为k-左偏树。所谓的k-左偏树是指一棵有k 个叶子的树&…

[51nod1274]最长递增路径

Description 一个无向图，每条边有一个边权。可以从任何点出发，任何点结束，可以经过同一个点任意次。走过的路必须满足所有边的权值严格单调递增，求最长能经过多少条边。 n,m<50000 Solution 既然它是要求严格单调递增&…

[51nod1327]棋盘游戏

###Description 给出一个n*m的棋盘，其中每一列可以放最多一个棋子。每一行有两个限制，left和right，表示这一行的前left个各自和后right个格子都有且仅有一个棋子。保证left和right没有交集。求放置棋子的方案数对1e97取模之后的结果。 n&l…

agc017f ZigZag

Description 给出n*(n1)/2个点，以三角形排列，每个点和其左下以及右下的点相邻。需要找出m条路径，每条路径都必须在前一条路径的右边。有一些规定，第i条路径的第j个位置必须向左/向右走求方案数 n,m<20 Solutoin 题目…

$【洛谷三月月赛R2】小清新签到题$

【洛谷三月月赛R2】小清新签到题

题目描述题目还是简单一点好。给定自然数n、k、x，你要求出第k小的长度为n的逆序对对数为x的1~n的排列，然后用仙人图上在线分支定界启发式带花树上下界最小费用流解决问题，保证存在。注：逆序对为满足、的。比较为字典序比较&…

bzoj 1499: [NOI2005]瑰丽华尔兹

Description 你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊…

Hello my friend

Description 给出一棵黑白树，你现在在一号节点。你现在有一个计数器，初始为0，每个时刻你需要进行如下操作 1：如果你所在的点为第一次到达或者为黑点则计数器1 2：等概率的走到和你所在的点相邻的点 3：…

[CF913F]Strongly Connected Tournament

Description 太长了自己看相信各位打过Hello 2018的dalao都知道题意我就不多讲了。 Solution 这道题比赛时没想真是亏了。。。首先根据一些竞赛图相关姿势我们知道汉密尔顿回路唯一且一定存在，那么这个条件就没有用了然后让我们来慢慢套路。首先设Fn表示…

Contest1796 - 2019年第二阶段我要变强个人训练赛第十五场 Problem B Reversi（DP）

链接：http://icpc.upc.edu.cn/problem.php?cid1796&pid1 题意：给你一个n，再顺序给出n个数，代表该位置上的颜色（数字）。可进行若干次染色操作（把相同数字之间的数全变为该数）。…

【NOIP2015模拟11.3】备用钥匙

Description 在一个公司里有n个职员。每一天被分成了m个时刻，每一个职员都会在每天的第Si个时刻出去，第Ti个时候回来。保证同一时刻不会有两个或以上的人出去/回来。这个公司有一把很神奇的锁，只能从里面开、关，从外面只能用钥…

背包九讲

背包九讲前言本篇文章是我(dd_engi)正在进行中的一个雄心勃勃的写作计划的一部分，这个计划的内容是写作一份较为完善的NOIP难度的动态规划总结，名为《解动态规划题的基本思考方式》。现在你看到的是这个写作计划最先发布的一部分。背包问题是一个经典…

【WC模拟】Equation

Description n,m<10^5 Solution 考虑图论转化，既然每个变量最多只会出现两次，那么我们把出现两次的变量所在的or组看做点，每个出现两次的变量看做边，边权视这两个变量是否相同而定。（0或1） 根据题目条…

【DP】354. 俄罗斯套娃信封问题

题目法1：DP，LIS问题基本方法，必须掌握！！！ class Solution {public int maxEnvelopes(int[][] envelopes) {int n envelopes.length;if (n < 2) {return n;}Arrays.sort(envelopes, (a1, a2) ->…

[CF891D]Sloth

Description 给出一棵n个节点的树，你需要删去并加入一条边，使得原图仍然是一棵树，并且有完美匹配。求方案数。 n<5*1e5 Solution 考虑枚举删去一条边，我们只需要统计某个子树内和外有多少个点可以成为匹配点。可以设Dp…

*POJ 1141 Brackets Sequence

题目描述分析： dp [ i ] [ j ] 表示添加括号的个数， path[ i][ j ] 表示 i ， j 中哪个位置分开，使得两部分分别匹配。 path[ i ][ j ] 为-1的时候，说明i, j 括号匹配。初始值置dp [ i ] [ i ] 1; 如果只有一个括…

D. Jellyfish and Mex - DP

题面分析： 题目最终需要达到MEX位0，也就是从最开始的MEX变成0后m的最小值，可以设 d p i dp_i dpi表示当前MEX为 i i i时，m的最小值，那么就可以根据前一个状态推出后一个状态，也就是假如当前MEX是 i i …

dp入门：从暴力dfs到dp

本篇为小金鱼大佬视频的学习笔记，原视频链接：https://www.bilibili.com/video/BV1r84y1379W?vd_source726e10ea5b787a300ceada715f64b4bf 基础概念暴力dfs很多时候仅能过部分测试点，要想将其优化，一般以 dfs -> 记忆化搜索 …

每日OJ题_算法_前缀和⑦_力扣525. 连续数组

目录力扣525. 连续数组解析代码力扣525. 连续数组 525. 连续数组难度中等给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。示例 1: 输入: nums [0,1] 输出: 2 说明: [0, 1] 是具有相同数量 0 和 1 的最…

最大连续子序列（HDU - 1231）

这是一个dp动态规划的题，上次写了一个最长连续子序列，今天又写了一个最大连续子序列，哈哈… 题目： 给定K个整数的序列{ N1, N2, …, NK }，其任意连续子序列可表示为{ Ni, Ni1, …, Nj }，其中 1 < i <…

点分治维护dp+连通块上新型dp思路+乘积方面进行根号dp：0922T4

首先连通块，所以点分治肯定是 Trick1 钦定选根的连通块dp 对于钦定选根的连通块dp，有一种常见思路先对原树求其dfn序，按dfn序倒序求解具体的，对于当前点 i i i（注意这里都是指dfn序），我们…

【DP动态规划】最长子序列

问题描述： 解题分析： 采用 DP 动态规划的方法： 先设置 f（1）1； 其次在计算出 f（2），再依次计算出后续的 f 的数值例F(3)是如何计算出来的： 首先判断a【3】是否…

智力竞赛（hiho145周）

题目介绍小Hi、小Ho还有被小Hi强拉来的小Z，准备组队参加一个智力竞赛。竞赛采用过关制，共计N个关卡。在第i个关卡中，小Hi他们需要获得Ai点分数才能够进入下一关。每一关的分数都是独立计算的，即使在一关当中获得超过需要的分数&a…

【YBT2023寒假Day12 B】仰望星空（DP）（线段树）（笛卡尔树）

仰望星空题目链接：YBT2023寒假Day12 B 题目大意有一个 n*n 的网格，第 i 列下面的 ai 个点都是障碍。然后又一些不是障碍的地方有特殊点，删掉它有费用。要你用最小费用使得不存在两个特殊点在一个矩阵中且矩阵中没有障碍。思路注意…

2016XTU算法专题个人赛4 题解

2016XTU算法专题个人赛4 题解 A. HDU 3664 Permutation Counting 题意： 给你一个{1, 2, …, N} 的排列a1,a2,…aN，我们定义这个排列的E值为其中ai>i的元素的数量。请你找出{1, 2, …, N} 有多少个E值为k的排列(对1,000,000,007.取模)。解法&#…

E. Masha-forgetful（dp）

题目：Problem - E - Codeforceshttps://codeforces.com/contest/1624/problem/E 题意： 玛莎认识了一个新朋友，并知道了他的电话号码 s 。电话号码是一个长度为m的字符串，它由从 0-9 组成。电话号码可能以 0 开头。玛莎已经…

THUPC2023 初赛(最后的活动-dp概率二分)

[THUPC 2023 初赛] 最后的活动题目背景各位亲爱的《La Lumire: Scarlet Intense Flame》玩家： 感谢您一直给予《La Lumire: Scarlet Intense Flame》的支持与厚爱。我们非常遗憾地宣布，《La Lumire: Scarlet Intense Flame》将于 2023 年 3 月 5 日…

西行妖

Description 给出一棵树，你可以让最多s个叶子节点被染色。然后，如果一个节点的儿子至少有一个被染色，那么他也会被染色。如果一棵树有大于等于m个被染色的点，那么这棵树就是美丽的。问给出一棵树，有多少种染色方…

【重点】【DP】123.买卖股票的最佳时机III

题目法1：单次遍历，Best! class Solution {public int maxProfit(int[] prices) {int f1 -prices[0], f2 0, f3 -prices[0], f4 0;for (int i 1; i < prices.length; i) {f1 Math.max(f1, -prices[i]);f2 Math.max(f2, f1 prices[i]);f3 Ma…

wqs二分+斜率优化：1019T4 / P9338

https://www.luogu.com.cn/problem/P9338 考虑暴力前 i i i 个分 j j j 段 f i , k f j − 1 , k − 1 g j , i f_{i,k}f_{j-1,k-1}g_{j,i} fi,kfj−1,k−1gj,i， O ( n 3 ) O(n^3) O(n3) 然后划分段数，段数显然越多越优，那么就上…

HUD 1114 Piggy-Bank 存钱罐（完全背包动态规划DP）

传送门：HDU 1114 题目大意：有一个存钱罐，已知它的净重和存满钱时候的重量，有n种不同规格的钱币，每种有一个重量和价值且数量不限，问当存钱罐存满钱的时候钱最少的价值是多少。前置技能：背包九…

HDU-1231 最大连续子序列(单调队列模板或 dp)

链接：http://acm.hdu.edu.cn/showproblem.php?pid1231 题意：多组样例，以0结束。给你一个n，接下来n个数，求出这n个数的最大连续子序列的和以及这个连续子序列的下标(l,r)，要求这个l，r尽可能的小…

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛L

K序列链接：https://www.nowcoder.com/acm/contest/91/L 来源：牛客网题目描述给一个数组 a，长度为 n，若某个子序列中的和为 K 的倍数，那么这个序列被称为“K 序列”。现在要你对数组 a 求出最长的子序列的长度&…

合唱队形问题

更好的阅读体验合唱队形。题目：合唱队形 N 位同学站成一排，音乐老师要请其中的 (N−K)位同学出列，使得剩下的 K 位同学排成合唱队形。合唱队形是指这样的一种队形：设 K 位同学从左到右依次编号为 1，2…&#xff0c…

LeetCode 0746. 使用最小花费爬楼梯：动态规划（原地）——不用什么从递归到递推

【LetMeFly】746.使用最小花费爬楼梯：动态规划（原地）——不用什么从递归到递推力扣题目链接：https://leetcode.cn/problems/min-cost-climbing-stairs/ 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向…

判定转状态+序列问题上树形dp：0909T2

考虑没有括号怎么做。对于这类*表达式求值问题，正常思考的dp是状态 O ( n ) O(n) O(n)，总共为 O ( n 2 ) O(n^2) O(n2) 的但其实可以对于每个dp记录两个值，分别为答案dp，和后面的乘积和g 如果接乘号，就是 [ j …

【LeetCode每日一题合集】2023.8.14-2023.8.20（⭐切披萨3n块披萨）

文章目录 617. 合并二叉树833. 字符串中的查找与替换（模拟）2682. 找出转圈游戏输家（模拟）1444. 切披萨的方案数（⭐⭐⭐⭐⭐）解法——从递归到递推到优化（二维前缀和记忆化搜索） 1388…

杭电ACM——2566，统计硬币（DP）

这道题似乎还可以用母函数做出来，不过当时懒得思考，就直接用DP做了。其实这是一道二维费用的背包模型。 dp[i,j,k]:用前i种硬币，用j个硬币，构成总面额k的最大方案数 dp[i,j,k] if(k<num[i]) dp[i-1,j,k]（表示当前总…

牛客15669，躲藏（DP）

题意：在一段字符串中，Cwbc作为子序列出现了多少次（不分大小写）。首先因为只找Cwbc，可以先进行预处理，把原串s[n]去除掉其他字母，形成只包含c,w,b三种字符的串s0[m]，接下来对s0进行D…

牛客小白月赛34 A dd爱科学1.0

题面题解 f [i] [j] : 已经处理到了前 i 个字母，第 i 个字母是 j 的最小花费因为这个序列是非递减的，所以前一个不能大于后一个，直接枚举第 i -1 个字母是什么，来转移方程代码 #include<bits/stdc.h>using namespace st…

2019牛客暑期多校训练营（第五场）G（DP）

题意：给定一个长度为n，m的只包含’0’~9’的字符串s[n],t[m]，问s[n]中有多少个子序列的大小（不含前导0）比t[m]大。本题要分类讨论，无分类讨论的话，会复杂很多。 1.s[n]中子序列长度大于m的情况…

最长公共子序列（上海交通大学考研机试题）

题目描述给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。注意： 第一个序列中的所有元素均不重复。第二个序列中可能有重复元素。一个序列中的某些元素可能不…

我敢说：你一定也没看到过这么复杂的算法题（Java实现LeetCode LCP 13 寻宝（分队列+BFS+DP））

LCP 13. 寻宝我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 ‘S’ 表示），和唯一的宝藏地点（用…

AcWing算法提高课-4.1.2搭配购买

算法提高课整理 CSDN个人主页：更好的阅读体验原题链接题目描述 Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有 n n n 朵云，云朵被编号为 1 , 2 , … , n 1,2,…,n 1,2,…,n，并且每朵云都有一个价值。但是商店…

2019牛客暑期多校训练营（第一场） E ABBA

dp[i][j]表示的是当有i个A，j个B时，符合要求的字符串数。转移方程详情看注释。参考博客：https://blog.csdn.net/chenshibo17/article/details/96455518 #include <bits/stdc.h> #define ll long long using namespace std; const int…

LeetCode 1014. 最佳观光组合

原题目：https://leetcode-cn.com/problems/best-sightseeing-pair/ 思路： 我们可以分析如下结果，对于i要分析[0,i-1]，对于i1，要分析[0,i] 对于i来说，a[left] left - a[i] - i; 那么对于i1来说&#xff…

【算法】状态机DP 买卖股票系列

文章目录前期知识股票问题买卖股票的最佳时机 II最佳买卖股票时机含冷冻期买卖股票的最佳时机 IV补充：恰好k次 / 至少k次怎么做？ 相关题目练习买卖股票的最佳时机 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/解法1——状态机DP解法…

Codeforces Round 768 (Div. 1) D. Flipping Range（思维题等价类性质 dp）

题目思路来源官方题解洛谷题解题解可操作的最短区间长度肯定是gcd，记为g，然后考虑如何dp 考虑g个等价类，每个等价类i,ig,i2*g,... 每次翻转长度为g的区间，会同时影响到g个等价类总的翻转的奇偶性， 性质一&…

【算法】最长公共子序列编辑距离（两个序列之间的DP）

文章目录最长公共子序列（LCS）编辑距离（Edit Distance）总结相关题目练习583. 两个字符串的删除操作 https://leetcode.cn/problems/delete-operation-for-two-strings/712. 两个字符串的最小ASCII删除和 https://leetcode.cn/prob…

蓝桥杯练习题总结（三）线性dp题（摆花、数字三角形加强版）

目录一、摆花思路一： 确定状态： 初始化： 思路二： 确定状态： 初始化： 循环遍历： 状态转移方程： 二、数字三角形加强版一、摆花题目描述小明的花店新开张，为了吸…

分治类dp：1017T3

http://cplusoj.com/d/senior/p/SS231017C 感觉可以分治某个区间 [ l , r ] [l,r] [l,r]，且他们都是在下面 k k k 已经选的基础上然后肯定要枚举最大值，最大值越长越好 Hint 1 Hint 2 f ( l , r , k ) f(l, r, k) f(l,r,k) 可以通过枚举 m i d mid…

dierti

题目描述询问如下多重集（数字可以重复的集合）的个数： 这个集合中有n个数字，每个数字在1..L之间，n为偶数。这n个数字能分成n/2组，使得每组有两个数，且这两个数的积不超过c。答案很大&#xff…

图论+博弈论上dp：CF536D

此题其实比较板，只是我没看出来首先肯定要跑个最短路，然后发现可以离散化把值域缩小然后 n n n 很小，直接暴力列个 n 2 n^2 n2 dp。转移要注意的是必须从大往小dp。从小到大会产生后效性。然后拿个双指针优化下转移就行。 // LUOG…

UI设计师不可不知的安卓屏幕知识

原文地址：http://www.zcool.com.cn/article/ZNjI3NDQ.html?fromsinglemessage&isappinstalled0你是安卓应用UI设计师吗？你是否被安卓手机纷繁的屏幕搞得晕头转向？你知道在什么尺寸中设计效果图经济有效吗？你知道屏幕密度是怎…

可删除背包（计数类）=＞转移数组进行展开：ABC321F

https://atcoder.jp/contests/abc321/tasks/abc321_f 还真没见过这个套路，呜呜┭┮﹏┭┮ 首先加就正常加，从后往前但删的话应该是从前往后减为什么呢？ 先写一下自己的理解，加要从后往前加是为了防止加多次减的话为了保证…

Leetcode.1014 最佳观光组合

题目链接 Leetcode.1014 最佳观光组合 Rating ： 1730 题目描述给你一个正整数数组 values，其中 values[i]表示第 i个观光景点的评分，并且两个景点 i和 j之间的距离为 j - i。一对景点（i<j）（i <…

codeforces 1526 C

题面题意给你一个长度为n的序列a，你的初始生命值为0，你可以选择加上ai,但前提是保证在任何时刻生命值不小于0. 求最多能加多少个值。C1版本的的n为2000，C2版本的n为20000 C1题解 C1的n只有2000，可以直接用dp来做，f…

选数异或（2023寒假每日一题 8）

给定一个长度为 nnn 的数列 A1,A2,⋅⋅⋅,AnA_1,A_2,,A_nA1,A2,⋅⋅⋅,An 和一个非负整数 xxx，给定 mmm 次查询，每次询问能否从某个区间 [l,r][l,r][l,r] 中选择两个下标不同的数使得他们的异或等于 xxx。输入格式输入的第一行包含三个整数 n,m…

hdu 2089 数位DP

不要62 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 41166 Accepted Submission(s): 15001 Problem Description 杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通…

NYOJ104/POJ1050——最大和

最大和时间限制：1000 ms | 内存限制：65535 KB 难度：5 描述给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵…

连续最大积 HDU - 4561

连续最大积 HDU - 4561 小明和他的好朋友小西在玩一个游戏，由电脑随机生成一个由-2，0，2三个数组成的数组，并且约定，谁先算出这个数组中某一段连续元素的积的最大值，就算谁赢！ 比如我们有如下随…

Codeforces Round #247 (Div. 2) C. k-Tree

*1600第二题，慢慢做，慢慢想。题目链接：点击打开原题目题意：给一个数字k，用它构造一棵树，构造方法是，从根节点开始往下，每个节点都有k个子节点（所以这棵树的深度是无限…

wqs二分

前提：答案满足凸性题目类似为 n n n 个里面选 m m m 个求某种代价，暴力二维dp复杂度大，但容易计算不限制选的次数。由于不限制选的次数，所以给选一个东西给一个代价 v v v，然后判断最后选了多少个，再…

【NOIP2016提高A组模拟9.15】Osu

Description 在平面直角坐标系中有n个点会依次出现，其中第i个点在第ti秒出现在(xi,yi)。你第0秒在(0,0)，求至少踩k个点的情况下你移动的速度的最大值最小是多少。答案输出a,b,c，表示ab√cn,k<2000 Solution 既然是双最值&#xff0…

【NOIP2013模拟】粉刷匠

Description 给出n个球，其中有C1个球是颜色1的，有C2个球是颜色2的，有C3个球是颜色3的…… 有Ck个球是颜色k的。求相邻两个球颜色不同的排列方案。 k<15,ci<6,数据组数<2000 Solution 这种题一般很难有直接的通式，可…

HDU_2191_背包问题

Description 急！灾区的食物依然短缺！ 为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等&…

bzoj 3791: 作业

Description 众所周知，白神是具有神奇的能力的。比如说，他对数学作业说一声“数”，数学作业就会出于畏惧而自己完成；对语文作业说一声“语”，语文作业就会出于畏惧而自己完成。今天，语文老师和数学老师…

C++数位动态规划算法：统计整数数目

题目给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数： num1 < x < num2 min_sum < digit_sum(x) < max_sum. 请你返回好整数的数目。答案可能很大&…

$AtCoder Beginner Contest 221 H. Count Multiset（容斥 dp 拆分数差分数形结合）$

AtCoder Beginner Contest 221 H. Count Multiset（容斥 dp 拆分数差分数形结合）

题目给定m,n(m<n<5e3)， 求大小为k的多重集合，满足元素和为n， 且每种数在集合中出现的次数都小于等于m的集合数有多少个答案对998244353取模思路来源官方题解「解题报告」[ABC221H] Count Multiset - K8He - 洛谷博客 Solu…

【done】剑指offer46_new：解密数字

题目：力扣165，https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/description/ 现有一串神秘的密文 ciphertext，经调查，密文的特点和规则如下： 密文由非负整数组成数字 0-25 分别对应字母 a-z 请…

bzoj 3357: [Usaco2004]等差数列

Description 约翰发现奶牛经常排成等差数列的号码．他看到五头牛排成这样的序号：“1，4，3，5，7”很容易看出“1，3，5，7”是等差数列．给出N(1≤N≤2000)数字AI..AN…

C++解题报告：电话网络——巧用树形DP

电话网络题目描述 Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。不过，为此FJ必须在奶牛们居住的N(1 < N < 10,000)块草地中选一些建上无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N …

leetcode 第360场周赛

总结好久没参加leetcode周赛了，比赛时间都从两小时变成了一个半小时。这次周赛由两道签到题和两道中等难度题组成，严格来说最后一道的难度也可以视为hard，但是只要想到正确的思路，编码还是比较容易的。比赛链接:leetcode 第 3…

hdu 4616 Game (树形dp）

Game Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2007 Accepted Submission(s): 649 Problem Description 　　Nowadays, there are more and more challenge game on TV such as ‘Girls, Rush Ahead’. No…

Android中自定义View时尺寸需要注意的相关事项

前些天发现了一个蛮有意思的人工智能学习网站,8个字形容一下"通俗易懂，风趣幽默"，感觉非常有意思,忍不住分享一下给大家。 👉点击跳转到教程在Android中自定义View时，一定要用dp或者sp不要用px，这样在不同的…

【DP】931. 下降路径最小和

题目法1：标准DP class Solution {public int minFallingPathSum(int[][] matrix) {if (matrix.length 0 || matrix[0].length 0) {return 0;}int m matrix.length, n matrix[0].length;int[][] dp new int[m][n]; // 到达i,j的最小路径和int min Integer.M…

不完全考虑构造+dp与构造：1107T2

http://cplusoj.com/d/senior/p/SS231107B 发现reverse操作会对一堆数进行修改，但如果我们只关注其中一些数呢？ 假设我们已经构造好 [ 1 , i − 1 ] [1,i-1] [1,i−1]，我们现在尝试构造 [ i , n ] [i,n] [i,n]，我们可操作的范…

10、动态规划相关

文章目录动态规划1、理论定义解题步骤debug2、基础问题leetcode 509. 斐波那契数leetcode 70. 爬楼梯leetcode 746. 使用最小花费爬楼梯leetcode 62. 不同路径leetcode 63. 不同路径 IIleetcode 343. 整数拆分leetcode 96. 不同的二叉搜索树3、背包问题01背包(二维数组)01背包(…

pytorch单精度、半精度、混合精度、单卡、多卡（DP / DDP）、FSDP、DeepSpeed模型训练

pytorch单精度、半精度、混合精度、单卡、多卡（DP / DDP）、FSDP、DeepSpeed（环境没搞起来）模型训练代码，并对比不同方法的训练速度以及GPU内存的使用代码：pytorch_model_train FairScale（你真…

蓝桥杯每日N题 (砝码称重)

大家好我是寸铁希望这篇题解对你有用，麻烦动动手指点个赞或关注，感谢您的关注不清楚蓝桥杯考什么的点点下方👇 考点秘籍想背纯享模版的伙伴们点点下方👇 蓝桥杯省一你一定不能错过的模板大全(第一期) 蓝桥杯省一你一定不…

LeetCode 2312.卖木头块：动态规划(DP)

【LetMeFly】2312.卖木头块：动态规划(DP) 力扣题目链接：https://leetcode.cn/problems/selling-pieces-of-wood/ 给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] [hi, …

数据结构-线段树

数据结构-线段树概述源代码概述线段树是一颗平衡的二叉搜索树，他以空间换区时间，让线性查找加速log级别的查找，用到的算法主要是二分搜索和递归。例如：有数组data[]{1,2,3,4}, 我有一个需求，我需要频繁的查找区间i~…

数位DP模板详解（转

// pos 当前处理的位置(一般从高位到低位) // pre 上一个位的数字(更高的那一位) // status 要达到的状态,如果为1则可以认为找到了答案,到时候用来返回, // 　　给计数器1。 // limit 是否受限,也即当前处理这位能否随便取值。如567,当前处理…

小美的01串翻转 - DP

题面分析： n的范围很小，可以进行dp，设dp[i][0] 表示第i个位置不进行反转得到的最大权值和，dp[i][1]表示第i个位置反转的最多权值和，那么可以枚举左右端点，每次更换左端点都清空dp数组，记录以…

初识动归（DP）：POJ3176--Cow Bowling

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程最优化的数学方法，也是ACM竞赛中最常用的算法之一。运用动态规划的题目常常会存在从状态i到状态i1的递推关系，找出这个状态转移方程是这类题目的核心。本题中，将牛…

C/C++每日一练(20230222)

目录 1. 部分复制字符串(★) 2. 按字典顺序排列问题(★★) 3. 地下城游戏(★★★) 附录动态规划 1. 部分复制字符串将字符串2小写字母复制到字符串1：编写程序,输入字符串s2,将其中所有小写字母复制到字符串数组strl中。例如：aal1bb22cc33de4AA55…

动态规划(DP)理论

上一篇专栏主要用几个程序来解释了回溯和动态规划之前的区别，但是没有说出动态规划本质的特色，就像贪心算法的三个步骤一样，直抒胸臆，于是这篇专栏便会主要围绕着解题思路来讲，目的就是让大家明白什么样的问题可以使用…

动态规划(DP)算法初识

先用大白话来说一下几种经典算法大概的意思： 贪心算法：我就一次机会，为了达到目的，其他的我啥也不考虑回溯算法：我有无数次机会，还能怕我有达不到目的的时候？动态规划算法：我能随意…

【GDOI2017模拟9.9】[IOI2007]偶环

Description 给定一个n个点m条边的无向带权图，你需要删除若干条边，使得这个图中没有长度为偶数的简单环。有一些边不能删除，保证不能删除的边构成原图的一个生成树。 n<1000,m<5000,每个点的度数<10 Solution 首先我们把那些本…

[ZJOI2016]线段树

Description 给出一个长度为n的序列，对这个序列进行m次操作，每次操作随机一个区间[l,r]，把这个区间里面的数全部变成这些数的最大值。求最后每个位置的数的期望，答案乘上(n(n1)/2)^m后对1e97取模 n,m<400，a[i]&…

【GDOI2017模拟9.24】周末晚会

Description 求n个点的圆排列，每个点是1或0，并且连续的0不超过k个的方案数。循环同构算一种。多组数据。 T<50,n,k<2000 Solution 首先，先不考虑环的情况，我们来处理一下连续的k个。一个很显然的想法是，…

接龙序列（14届）

对于一个长度为 K 的整数数列：A1,A2,...,AK，我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1的末位数字 (2≤i≤K2≤i≤K)。例如 12,23,35,56,61,11 是接龙数列；12,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34…

二分队列+决策单调性优化dp：P6246

https://www.luogu.com.cn/problem/P6246 决策单调性若 d p i dp_i dpi 由 j j j 转移，则 d p i 1 dp_{i1} dpi1 转移点 k k k 满足 k ≥ j k\ge j k≥j 发现决策点满足单调，但遍历的点不满足单调，不能用双指针，考虑…

题解：ABC320F - Fuel Round Trip

题解：ABC320F - Fuel Round Trip 题目链接：Atcoder。链接：洛谷。难度算法难度：B。思维难度：A。调码难度：A。综合评价：普及/提高（个人认为评为提高/省选-是合理的&…

概率DP[NOIP2016D2T3换教室]

YZOJ 概率DP最现实的体现就是数学期望的求解。 1.数学期望的定义： 数学期望是试验中每次可能结果的概率乘以其结果的总和，反映了随机变量平均取值的大小。 2.离散型随机变量的数学期望。当随机变量有限或无限但有一定次序，那么称为离散…

【LeetCode:2646. 最小化旅行的价格总和 | DFS + DP】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨ 🌲 作者简介：硕风和炜，…

2月12日刷题总结

分割等和子集题目描述给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1：输入：nums [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [1…

【蓝桥杯集训26】线性DP（4 / 4）

目录 898. 数字三角形输出最优路径 895. 最长上升子序列 897. 最长公共子序列 1051. 最大的和 - 前后缀分解dp 898. 数字三角形输出最优路径活动 - AcWing 题目： 给定如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至…

Leetcode.1638 统计只差一个字符的子串数目

题目链接 Leetcode.1638 统计只差一个字符的子串数目 Rating ： 1745 题目描述给你两个字符串 s和 t，请你找出 s中的非空子串的数目，这些子串满足替换一个不同字符以后，是 t串的子串。换言之，请你找到 s和 t串中恰…

模拟赛轰炸

题目大意有 nnn 座城市，城市之间建立了mmm 条有向的地下通道。你需要发起若干轮轰炸，每轮可以轰炸任意多个城市。但每次轰炸的城市中，不能存在两个不同的城市 iii，jjj 满足可以通过地道从城市 iii 到达城市 jjj。你需要求出…

CF632E Thief in a Shop 题解

CF632E Thief in a Shop 题解前驱题目链接字面描述题面翻译输入输出格式输入格式：输出格式： 输入输出样例输入样例#1：输出样例#1：输入样例#2：输出样例#2：输入样例#3：输出样例#3： 思…

【算法】01背包和完全背包

文章目录背包问题概览01背包二维dp数组写法一维dp数组写法完全背包关于遍历顺序相关题目[416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/)[279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)[518. 零钱兑换 II](https://leet…

$NYOJ110 剑客决斗$