dp专题
上海邀请赛 A题目 HDU 5236（dp）
先求出没有ctrl+s的时候构造长度为i的期望f[i] 。然后枚举保存的次数，求出最小即可。 #include<cstdio>#include<cstdio>#include<cmath>#include<queue>#include<stack>#include<string>#include<cstring>#include<iostream>#include<map>
poj 3160 Father Christmas flymouse 强连通+dp
首先我们可以确定的是，对于val值小于0的节点都变成0. 假设一个集合内2个房间都能任意到达，那么我就可以吧集合内的所有点的价值都取到，并且可以达到任一点。实际上集合内的每个点是相同的，这样的集合就是一个强连通分量。 那么我们就可以用tarjin算法进行强连通缩点， 最后形成一个dag的图。在dag的图上面进行dp。可以先用拓扑排序后dp。或者建反响边记忆化搜索 。 VIEW
秋招突击——6/22——复习{区间DP——加分二叉树，背包问题——买书}——新作{移除元素、实现strStr（）}
文章目录 引言复习区间DP——加分二叉树个人实现 背包问题——买书个人实现参考实现 新作移除元素个人实现参考思路 找出字符串中第一个匹配项的下标个人实现参考实现 总结 引言 今天做了一个噩梦，然后流了一身汗，然后没起来，九点多才起床背书。十点钟才开始把昨天那道题题目过一遍，然后十一点才开始复习题目，为了不耽误下午的时间，所以这里的就单纯做已经做过的题目，主打一个有量，不在学
动态规划DP--斐波那契数、爬楼梯、使用最小花费爬楼梯等示例代码
动态规划DP 文章目录 动态规划DP509. 斐波那契数70. 爬楼梯746. 使用最小花费爬楼梯62. 不同路径63. 不同路径II343.整数拆分 509. 斐波那契数 509. 斐波那契数 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) =
状态压缩DP——AcWing 291. 蒙德里安的梦想
状态压缩DP 定义 状态压缩DP是一种利用二进制数来表示状态的动态规划算法。它通过将状态压缩成一个整数，从而减少状态数量，提高算法效率。 运用情况 状态压缩DP通常用于解决具有状态转移和最优解性质的问题，例如组合优化、图论、游戏等问题。它的基本思想是将问题的状态表示为一个二进制数，其中每一位表示一个元素或一个状态。通过对二进制数的位运算，可以方便地进行状态转移和最优解的计算。 注意事项
算法基础精选题单 动态规划（dp）（区间dp）（个人题解）
目录 前言： 正文： 题单：【237题】算法基础精选题单_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网 (nowcoder.com) NC50493 石子合并： NC50500 凸多边形的划分： NC235246 田忌赛马： NC13230 合并回文子串: NC16645 [NOIP2007]矩阵取数游戏： NC207781 迁徙
[CQUOJ 21448] 会做题的兔兔 （数学+DP）
题意大意是有一个整数，可以用若干个 2的 n次幂累加得到，问一共有多少种累加方案 统计方案的题，最重要的是做到不重复，不遗漏 dp[i][0]表示构成 i中不含 1的方案有多少种 dp[i][1]表示构成 i中含 1个 1的方案有多少种 dp[i][2]表示构成 i中含 1的方案有多少种 最后答案是 dp[N][0] +dp[N][2] 思路如下： 1) 如果 i是奇数，那么必然要有
[CQUOJ 21412] 软妹币！软妹币！软妹币！ （数学+DP）
CQUOJ - 21412 题意大致是，用若干不同的数中的某些数加减得到 1…n之间的所有数，需要的最少几个不同的数 赛上是找规律做的，虽然过了，但是感觉不太稳，赛后看了题解恍然大悟 首先有这样一个事实，如果有 3个数可以表示 1..13 那么对于小于 13的n，答案至多为 3 所以我们可以考虑，用 i个数能够构造出的最大的数是多少 设 dp[i]表示 i个数最大能表示 [1, dp[
[SCU 4516] Mingo's Game （斜率DP）
SCU - 4516 有 N个关卡，可以分为 K块，每个关卡都有个权值 ti t_i 每次选择最早没有通关的关卡块，设这个关卡包含了 [i,j] [i,j]的游戏 选到最早没有通关的关卡是k, 选到 k的概率是 P=tk∑jx=ix P =\frac {t_k} {\sum_{x=i}^j x} 选到一个关卡一定能通关，花费一小时 求合理分块的情况下，通关所有关卡块的期望时间最小
[SCU 4515] 又见背包 （可行性背包DP）
SCU - 4515 有 N个大小不同的数字，第 i种数字为 a_i，每种有 m_i个 求问能否从中选出若干个数字，使他们的和为 K 背包九讲 2.0的例题，用多重背包的二进制能过 根据 lyb dalao所述 因为 K<1e5 K<1e5，所以其实最后用到的物品数量不会超过 1e5 所以 mi=min(mi,K/ai) m_i = min(m_i, K/a_i)，所以用
[LightOJ 1364] Expected Cards （高维期望DP）
LightOJ - 1364 一副扑克牌，不断地从中抽牌 要求四种花色都至少要有给定的张数 其中如果抽到了王牌，可以将其变为任意花色 求满足条件时，抽出的期望张数 刚开始想错了，两张王牌并非在一开始就给定了 而是在游戏中可以视当前情况选择着变的 这两种方式是不一样的 由于牌数其实并不会很多， 复杂度乘一乘发现才 107 10^7级别的，所以直接暴力DP 将两张王牌当
[LightOJ 1321] Sending Packets （SPFA+概率DP）
LightOJ - 1321 给定一张无向图，每条边都有一个通过的概率 如果无法通过，那么就要回到起点重新出发 从起点到终点的时间固定为 K K，如果成功到达， 又需要额外花费 KK的时间，问走 S S次的最小期望时间首先可以跑一遍SPFA求出一次通过的最大概率 pp 设跑一次的最小期望时间为 E E，E=p×2K+(1−p)×(E+2K)E = p\times 2K + (1-
[LightOJ 1274] Beating the Dataset （期望DP）
LightOJ - 1274 题目等价于，给定一个开头为 1的 01串， 求其中相邻两个字符不相等的期望对数 一开始煞笔了，其实 YES和 NO的个数是可以直接算出来的 算出来之后，设 dp[i][j][k] dp[i][j][k]为第 i i位，jj表示当前是 YES(1)或 NO(0) k k表示 ii位及以前一共有多少个 YES，然后倒着就推出来了 下一位出现 0
[HDU 5886] Tower Defence （树形DP）
HDU - 5886 给定一棵树，每条边都有一个权值 定义一条边的战术价值为割去这条边后 剩下的图中最长链的长度 求随机割掉一条边，战术价值的期望 题目要求乘以 N−1 N-1，所以直接把概率消掉了 所以只要求割去每条边后的最长链长度即可 这就转化为了一个树形dp 首先割去一条边 u−>v u->v 后，最长链可能在 v v 为根的子树中 这个简单地做一次树形dp
DP：完全背包+多重背包问题
完全背包和01背包的区别就是：可以多次选 一、完全背包（模版） 【模板】完全背包_牛客题霸_牛客网 #include <iostream>#include<string.h>using namespace std;const int N=1001;int n,V,w[N],v[N],dp[N][N];//dp[i][j]表示从前i个物品选，体积不超过j的最大价值//d
数位统计DP——AcWing 338. 计数问题
数位统计DP 定义 数位DP（Digital DP）是一种用于解决与数字的数位相关问题的动态规划算法。它将数字的每一位看作一个状态，通过转移状态来计算满足特定条件的数字个数或其他相关统计信息。 运用情况 统计满足特定条件的数字个数，例如在给定范围内有多少个数字满足某些数位特征。计算数字的某个数位上的特定统计信息，如出现的数字频率等。解决与数字排列、组合相关的问题。 注意事项 数位DP的
HDU 4800 DP
13长沙现场赛 DP 就是告诉你C(m,3)个队伍相互之间的胜率，然后要你依次对战n个AI队伍，首先任选一种队伍，然后战胜一个AI后可以选择替换成AI的队伍，也可以不换，问你最后最大的胜率是多少。 从最后一个对战开始DP dp[i][j]=a[j][b[i]]*max(dp[i+1][j],dp[i+1][b[i]]) #include "stdio.h"#inclu
HDU 2870 DP 最大完全子矩阵
HDU 1505 升级版 枚举a，b，c 各做一遍最大完全子矩阵 #include "stdio.h"#include "string.h"char a[1010][1010];int n,m,ans;int sum[1010][1010];int max(int a,int b){if (a<b) return b;else return a;}void solve(cha
POJ 1088 DP || 记忆化搜索
按高度从小到大排序一遍 DP即可: #include "stdio.h"#include "string.h"#include "queue"#include "algorithm"using namespace std;int dir[4][2]={1,0,-1,0,0,1,0,-1};int n,m,Min,ans;int a[101][101],dp[101][1
POJ 2955 区间DP
求最多能匹配的括号数*2 #include "stdio.h"#include "string.h"int max(int a,int b){if (a<b) return b;else return a;}int judge(char a,char b){if (a=='(' && b==')') return 1;if (a=='[' && b==']') return 1
POJ 1947 树形DP入门题
给出N个点，N-1个关系，建出树形图，问最少减去几个边能得到节点数为P的树。典型树形DP题 dp[cur][j] :记录cur结点，要得到一棵j个节点的子树去掉的最少边数 转移方程用的背包的思想 对当前树的每一个子树进行计算 砍掉此子树： dp[cur][j]=dp[cur][j]+1; 不砍掉： for (l=0;l<=j;l++) dp[cur]
POJ 3342 树形DP入门题
题目意思和POJ2342一样，只是多加了一个条件，如果最大方案数唯一，输出Yes，不唯一输出No dp的是时候多加一个变量记录答案是否唯一即可 #include "stdio.h"#include "string.h"#include "vector"using namespace std;struct node{int fa;vector<int>child;}da
POJ 3034 DP
打地鼠游戏中，你有一个锤子，每一秒钟你可以拿着锤子移动d个单位的距离，必须是直线，掠过的鼠洞中露出的地鼠都会被锤打至，而事先知道从开始时各时间段内出现在老鼠的数量和位置，问题是从游戏开始至结束时，你最多能打到多少只地鼠，开始时锤子可以在任何位置。 题目有个陷阱， 只是说Moles出现的坐标为正,但没说hammer移动的位置要为正,可以为"any position" 所以锤子可以移出矩阵
HDU 4901 DP背包
给你n个数，问你将数分成两个数组，S，T ，T 中所有元素的需要都比S任意一个大，问你S中所有元素进行 XOR 操作和 T 中所有元素进行 &操作值相等的情况有多少种。 DP背包思路 dpa[i][j][0] 表示从左开始到i，不取i，状态为j的方案数 dpa[i][j][1] 表示从作开始到i，取i，状态为j的方案数 dpb[i][j] 表示从右开始到i，状态为j的方案数
POJ 2948 DP
一个row*col的矩阵，每个格子内有两种矿yeyenum和bloggium，并且知道它们在每个格子内的数量是多少。最北边有bloggium的收集站，最西边有 yeyenum 的收集站。现在要在这些格子上面安装向北或者向西的传送带(每个格子自能装一种)。问最多能采到多少矿。 DP，状态转移方程为 dp[i][j]=Max(dp[i][j-1]+suma[i][j],dp[i-1]
POJ 2029 DP || 暴力
在大矩形中找一个小矩形 使小矩形包含的*最多 暴力或者DP 水题 暴力： #include "stdio.h"#include "string.h"int main(){int n,m,w,i,s,t,j,k,l,ans,sum,x,y;int map[101][101];while (scanf("%d",&w)!=EOF){if(w==0) break