P5241 序列（滚动数组+前缀和优化dp）
P5241 序列挺神仙的一题看看除了dp好像没什么其他办法了想着怎么构个具体的图出来，然鹅不太现实。于是我们想办法用几个参数来表示dp数组加了几条边肯定要的吧，于是加个参数$i$表示已加了$i$条边这显然是不够的。于是我们又想：强连通分量.....连通块.......于是加个$j$表示还有$j$个强...
hdu 4539(状态压缩dp)
题意：曼哈顿距离是指:|x1-x2|+|y1-y2|，只要知道这个概念题意就懂了。分析：这道题与前面做的几道题有所不同，因为当前行不仅与前一行有关，而且与前两行有关，所以我们开数组的时候还要记录前两行的状态，所以我们需要开设三维数组。代码实现：#include<cstdio>#inclu...
[BZOJ 1907] 树的路径覆盖 【树形DP】
题目链接：BZOJ - 1907题目分析使用树形 DP，f[x][0] 表示以 x 为根的子树不能与 x 的父亲连接的最小路径数（即 x 是一个折线的拐点）。f[x][1] 表示以 x 为根的子树可以与 x 的父亲连接的最小路径数。转移的方式非常巧妙，Orz PoPoQQQ 的 blog 。代码#i...
BZOJ 1649: [Usaco2006 Dec]Cow Roller Coaster( dp )
有点类似背包 , 就是那样子搞...------------------------------------------------------------------------------------#include<cstdio>#include<cstring>#in...
#DP# ----- OpenJudge山区建小学
没有记性。到DP不得不写博了，三天后又忘的干干净净。DP是啥 :-)一道久到不能再久的题了。OpenJudge 7624:山区建小学总时间限制: 1000ms 内存限制: 65536kB描述政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过...
ural 1057（数位dp）
数位dp题，关键是用树的思维去考虑。对于一个数字X，要是能表示成K个B的不同次幂，等价于X在B进制下有且只有K个位上面的数字为一，其他位上的数字都为0。具体读者可以去参考，国家集训队李聪的论文，里面的介绍都很详细。#include<stdio.h>#include<string.h...
【数位DP】[LOJ10163]Amount of Degrees
发现自己以前对数位DP其实一窍不通...这题可以做一个很简单的转换：一个数如果在$b$进制下是一个01串，且1的个数恰好有k个，那么这个数就是合法的（刚开始没判断必定是01串，只判断了1的个数竟然有60pts，数据可真的水~）这个结论显然成立，也不需要什么证明啦qaq~然后数位DP就好了转化为b进制...
SPOJ - BALNUM Balanced Numbers（数位dp+三进制状压）
Balanced NumbersBalanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:1) Every e...
Balanced Numbers （数位dp+三进制）
SPOJ - BALNUM题意：Balanced Numbers：数位上的偶数出现奇数次，数位上的奇数出现偶数次（比如2334, 2出现1次，4出现1次，3出现两次，所以2334是 Balanced Numbers） ，求一个区间内有多少Balanced Numbers。解题思路：看题很容易想到数位...
Jury Compromise POJ - 1015 dp （标答有误）背包思想
题意:从 n个人里面找到m个人 每个人有两个值 d p 满足在abs(sum(d)-sum(p)) 最小的前提下sum(d)+sum(p)最大思路：dp[i][j] i个人中 和是 j 运用背包的思想 二维背包 i是人数容量，人数要符合背包思想，每次只插入一个，逆序...
Ural Amount of Degrees（数位dp）
传送门Amount of DegreesTime limit: 1.0 secondMemory limit: 64 MBDescriptionCreate a code to determine the amount of integers, lying in the set [X;Y] and ...
hdu 2167(状压dp)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2167思路：经典的状压dp题，前后，上下，对角8个位置不能取，状态压缩枚举即可所有情况，递推关系是为dp[i][j]=max(dp[i][j],dp[i-1][k]+sum[i][j]),具体的含义见co...
Travel（HDU 4284状压dp）
题意：给n个城市m条路的网图，pp在城市1有一定的钱，想游览这n个城市（包括1），到达一个城市要一定的花费，可以在城市工作赚钱，但前提有工作证（得到有一定的花费），没工作证不能在该城市工作，但可以走，一个城市只能工作一次，问pp是否能游览n个城市回到城市1.分析：这个题想到杀怪（Survival（Z...
hdu 4739 状压DP
这里有状态压缩DP的好博文题目：题目比较神，自己看题目吧分析：大概有两种思路：1.dfs，判断正方形的话可以通过枚举对角线，大概每次减少4个三角形，加上一些小剪枝的话可以过。2.状压DP，先预处理出所有可以组成正方形的方案，根据题目的数据范围计算不会超过100个正方形方案。n个正方形用二进制的方式记...
hdu 2809(状压dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2809思路：简单的状压dp,看代码会更明白。 #include<iostream> #include<cstdio> #include<cstring> #includ...
HDU 3001 状压DP
有道状压题用了搜索被队友骂还能不能好好训练了，，hdu 3001 经典的状压dp大概题意。。有n个城市 m个道路 成了一个有向图。n<=10； 然后这个人想去旅行。有个超人开始可以把他扔到任意的一个城市。。然后他就在城市之间游荡。要满足他要游玩所有的城市。。并且。每个城市最多去两次。要求路程...
算法学习——决策单调性优化DP
update in 2019.1.21 优化了一下文中年代久远的代码 的格式……什么是决策单调性？在满足决策单调性的情况下，通常决策点会形如1111112222224444445555588888.....即不可能会出现后面点的决策点小于前面点的决策点这种情况。那么这个性质应该如何使用呢？1，二分。...
积木(DP)问题
问题：Do you remember our children time? When we are children, we are interesting in almost everything around ourselves. A little thing or a simple game ...
HW2016_字符串_STL_DP
一、在字符串str1中删除那些在str2中出现的字符。str2可能会有重复字符，直接遍历会导致效率低下，故先借助STL的set容器对str1查重；然后，遍历str1和str2，对str1进行查重。#include <iostream>#include <string>#inc...
2015南阳CCPC D - Pick The Sticks dp
D - Pick The SticksTime Limit: 1 SecMemory Limit: 256 MB题目连接无DescriptionThe story happened long long ago. One day, Cao Cao made a special order called...