dP

题意 从$1 - n$中任意选择一些数，选$m$次构成$m$个集合 保证： 集合不为空 任意两个集合不相同 集合内各个元素xor起来等于0 Sol 神仙题Orz 我看到两种做法，一种是洛谷题解上的直接dp，另一种是yyb的神仙转化。 其实都差不多吧。。 我简单说一下，设$f[i]$表示选了$i$个集 ...

题意 "题目链接" $n$个节点的树，点有点权，找出互不相交的两条链，使得权值和最大 Sol ~~这辈子也不会写树形dp的~~ 也就是有几种情况，可以讨论一下。。 下文的“最大值”指的是“路径上权值和的最大值” 设$f[i][0]$表示以$i$为根的子树中选出两条不相交的链的最大值 $f[i][1] ...

题意 "题目链接" Sol 很显然的一个dp方程 $f_i = min(f_j + (sum_i sum_j 1 L)^P)$ 其中$sum_i = \sum_{j = 1}^i len_j + 1$ 这个东西显然是有决策单调性的。 单调队列优化一下 我好像已经做过三个这种类型的题了，而且转移的时候 ...

题意 ~~[题目链接]~~版权原因就不发了。。 给出一棵树，求出任意两点之间期望距离的最大值 Sol 比较清真的一道题吧。。 设$f[x]$表示从$x$走到$x$的父亲的期望步数 $g[x]$表示从父亲走来的期望步数 $d[x]$表示$x$节点的度数 不难得到方程$f[x] = \sum_{to \ ...

题意 "题目链接" 给出$n$个数，问最少选几个数，使他们的$gcd = 1$ Sol 好神仙啊qwq。 首先，如果答案存在，那么最多为$7$(因为前$7$个质数乘起来$ = 3e5$) 考虑dp，设$f[i][j]$表示选了$i$个数，他们$gcd = j$的方案数！ 没错是方案数！ 那么我们只要 ...

题意 "题目链接" Sol 首先不难想到一个dp 设$f[i][j]$表示选了$i$个 严格递增 的数最大的数为$j$的方案数 转移的时候判断一下最后一个位置是否是$j$ $$f[i][j] = f[i][j 1] + f[i 1][j 1] j$$ cpp for(int i = 0; i usi ...

众所周知，斜率优化$DP$是很（mei）优（laun）秀（yong）的算法。 所以，就和博主一起来学习吧。 例题一：任务安排 【题目描述】 有$N$个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这$N$个任务分成若干批，每一批包含连续的若干个任务。从时刻$0$开始，任务被分批加 ...

题意 "题目链接" Sol 介绍一种神奇的点分治的做法 啥？这都有根树了怎么点分治？？ 嘿嘿，这道题的点分治不同于一般的点分治。正常的点分治思路大概是先统计过重心的，再递归下去 实际上一般的点分治与统计顺序关系不大，也就是说我可以先统计再递归，或者先递归再统计。 但是这题不单单是统计，它是dp，存在 ...

题意 "题目链接" Sol 首先考虑当$n = p^x$，其中$p$是质数，显然它的因子只有$1, p, p^2, \dots p^x$(最多logn个) 那么可以直接dp, 设$f[i][j]$表示经过了$i$轮，当前数是$p^j$的概率，转移的时候枚举这一轮的$p^j$转移一下 然后我们可以把每 ...

这一道题,我也是搞了很久才搞懂的~~(也就两个多小时)~~。 感谢Rayment大佬的题解! 我们进入正题。 对于一个笼子里的动物,我们可以选择撤走或不撤走,可以用0和1来表示,很容易就想到二进制,想到状压dp(为什么先选dp,看数据想想吧)。 观察题面,我们可以发现,小朋友最多可达五万人(动物园容 ...

题意 "题目链接" Sol 质数的限制并没有什么卵用，直接容斥一下：答案 = 忽略质数总的方案 没有质数的方案 那么直接dp，设$f[i][j]$表示到第i个位置，当前和为j的方案数 $f[i + 1][(j + k) \% p] += f[i][j]$ 矩乘优化一下。 cpp include de ...

题意 "题目链接" Sol 首先不难想到一种暴力dp，设$f[i][a][b][c]$表示还有$i$轮没打，场上有$a$个1血，$b$个2血，$c$个三血 发现状态数只有$s = 166$个，复杂度为$O(ns)$ 矩乘优化一下复杂度为$O(s^3 logn T)$，还是过不去。 因为每次询问都是独 ...

问题描述 插头dp用于解决一类可基于图连通性递推的问题。用插头来表示轮廓线上的连通性，然后根据连通性与下一位结合讨论进行转移。 表示连通性的方法 与字符串循环最小表示不同，这种方法用于给轮廓线上的联通情况确定一个唯一对应的标号序列，做法是从左至右轮廓线扫描，每扫描到一个未标号的位置就新建一个标号，并 ...

题意 "题目链接" Sol 这题可以动态dp做。 设$f[i]$表示以$i$为结尾的最大子段和，$g[i]$表示$1 i$的最大子段和 那么 $f[i] = max(f[i 1] + a[i], a[i])$ $g[i] = max(g[i 1], f[i])$ 发现只跟前一项有关，而且$g[i]从 ...

题意 "题目链接" Sol 可以把题目转化为从$[1, 2n + 1]$中选$k$个数，使其和为$(n+1)k$。 再转化一下：把$(n+1)k$划分为$k$个数，满足每个数在范围在$[1, 2n + 1]$ 这时候就可以用整数划分的思路dp了(然鹅我还是想不出来。。) 因为每个数互不相同，因此我们 ...

题意 "题目链接" Sol 神仙题Orz 考虑区间dp，如果我们只设$f[l][r]$表示$s_{lr}$被压缩的最小长度，而不去关心内部$M$分布的话，可能在转移的时候转移出非法状态 因此考虑多加一维表示当前子串中有没有$M$(默认第一个字符为$M$不统计在内) 转移的时候就考虑不同的$M$对当前 ...

题意 "题目链接" Sol 看到这种题就不难想到是数位dp了。 一个很显然的性质是一个数若能整除所有位数上的数，则一定能整除他们的lcm。 根据这个条件我们不难看出我们只需要记录每个数对所有数的lcm(也就是2520)取模的结果 那么$f[i][j][k]$表示还有$i$个数要决策，之前的数模$25 ...

题意 "题目链接" Sol 比赛结束后才调出来。。不多说啥了，就是因为自己菜。 裸的up down dp，维护一下一个点上下的直径就行，一开始还想了个假的思路写了半天。。 转移都在代码注释里 ~~毒瘤题目卡空间~~ cpp include define Pair pair define MP(x, ...

强烈安利gjz的题解，看一遍即可ac：传送门 进入重点： 为啥$to=(dp[i][k][ii]+dp[k+1][j][jj])/2$ 位运算重点：a&b=a+b-a|b 为啥呢？ 例子： a : 100101 b : 010101 a&b : 0　0　0　1　0　1 a+b : 1　1　1　0　1 ...

题目： "1003: [ZJOI2006]物流运输" 解析： 最短路+DP 我们用$no[i][j]$来表示$i$在第$j$天不可以经过 用$cost[i][j]$表示第$i$天到第$j$天的花费 在最短路的时候判断一下在第$i$天到第$j$天中哪些码头不可以走，在做最短路时跳过 最后设f[i]表示 ...

题目： "3209: 花神的数论题" 解析： 二进制的数位DP 因为$[1,n]$中每一个数对应的二进制数是唯一的，我们枚举$1$的个数$k$，计算有多少个数的二进制中有$k$个$1$ 设$n$的二进制一共有$num$位，有$sum[i]$个数的二进制中有$k$个$1$， 答案就是$\prod_{i ...

题目： " 10172. 「一本通 5.4 练习 1」涂抹果酱" 解析： 三进制的状压DP 经过简单的打表发现，在m=5时最多有48种合法状态 然后就向二进制一样枚举当前状态和上一层的状态进行转移就好了 由于第k行是给定的，所以转移时要特判一下第k行，并且注意下一k=1的情况 代码： cpp inc ...

板子整理 目录 排序（快排及其原理、sort、归并、以及STL中的compare写法） 递归（排列问题、dfs、斐波拉契） 二分（主要为例题） dp问题汇总（背包、子序列、树形dp例题等等） 计算几何（凸包、叉积） 图算法（最小生成树、最大流、最短路径、二分图） 字符串匹配（有限自动机、KMP） F ...

A - Range Flip Find Route 题意：本题就是给你一个矩阵，要你求出从（1，1）到（h，w）数量最少的黑色方块 题解：在作这一题的时候我最初想到的是用DFS求出每一种可能的方式，比较出它们的最小值，结果TLE了，赛后补题，才懂得还可以用DP来做：这里我们定义一个二维数组dp[h] ...

最佳买卖股票时机含冷冻期（中等）2020年7月10日题目来源：力扣解题需要好好理解状态量是当前收益，有三种状态：持股状态、不持股的冷冻期状态、不持股的卖出状态class Solution { public int maxProfit(int[] prices) { int plen=prices.length; int[][] dp=new int[plen+1][3]; if(plen<2) return 0; //

给定一个无序的整数数组，找到其中最长上升子序列的长度。示例:输入: [10,9,2,5,3,7,101,18]输出: 4解释: 最长的上升子序列是[2,3,7,101]，它的长度是 4。说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为O(n2) 。解题思路： 利用动态规划，设置一个dp数组，dp[n]代表以第n个元素结尾的字符串的最长上升子序列的长度，因此dp[n] = max(dp[s]+1),其中s<n且s[s] &...

题目描述二维背包问题，实际上套一维背包及后续优化模板即可。。。状态转移方程：开个坑先。。。代码如下：#include<iostream>#include<algorithm>using namespace std;int n, m, k;int ball[101] = { 0 }, hurt[101] = { 0 };int dp[1010][505] = { 0 };void findans() {int num = 0, life = m;dp[b

1.布局文件.xml <android.support.v7.widget.RecyclerView android:id="@+id/regionInfoRecycler" android:layout_width="match_parent" android:layout_height="0dp" android:visibility="visible" android:la

题意：爱丽丝和鲍勃正在玩游戏。有两个成堆的卡片。每一堆有N个卡片,每张卡片有一个分数。他们轮流接顶部或底部拿卡片,卡的分数将被添加到他的总分。爱丽丝和鲍勃都足够聪明,拿起牌来获得尽可能多的分数。爱丽丝先手最多能拿多少分?题解：经典博弈dp设置状态dp[l1][r1][l2][r2]：l1-r1：指第一堆余下的为从下面 l1 位置开始到 r1 位置l2-r2:同理dp[l1][r1][l2][r2]即为在这种状态下Alice的最多得分总共可以从四个状态转移过来，第一堆取最后一个/最顶上一个，第二堆

Android Vector Asset在网上一直没找到这两个图标❌ ✔，找到的都不是免费的，只能动手画了ic_right.xml<vector xmlns:android="http://schemas.android.com/apk/res/android" android:width="24dp" android:height="24dp" android:viewportWidth="24" android:viewportHeight="24"