Luogu 1060 开心的金明 / NOIP 2006 （动态规划）
Luogu 1060 开心的金明 / NOIP 2006 （动态规划） Description 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始...
【HNOI2004】 敲砖块 动态规划
题目描述： 在一个凹槽中放置了 n 层砖块、最上面的一层有n 块砖，从上到下每层依次减少一块砖。每块砖 都有一个分值，敲掉这块砖就能得到相应的分值，如下图所示。 14 15 4 3 23 33 33 76 2 2 13 11 22 23 31 如果你想敲掉第 i 层的第j 块砖的话，...
bzoj 1190: [HNOI2007]梦幻岛宝珠 动态规划
根据题意，很明显需要把a*2^b中b相同的先分成一组，然后首先得到这一组中的答案。 然后如果令f[m]表示当重量为m时的最大值，那么考虑将第k组加入其中，由于第k组的重量一定<=1000*2^k，可以发现只有m的二进制中的10位左右会受到影响。然后dp就好了。 AC...
BZOJ 1190 HNOI2007 梦幻岛宝珠 动态规划
题目大意：01背包，其中weight<=2^30,但是每个weight都能写成a*2^b的形式，其中a<=10,b<=30 直接背包肯定TLE+MLE 考虑到每个weight都能写成a*2^b的形式，显然我们要按照b分层来进行背包 令f[i][j]表示有j*2^i+(w&(...
动态规划学习系列——数位DP（练手三）
题目链接：HDU 3652 解题思路： 数位DP，状态 dp[i][j][k][c]表示 i 位数中，以 j 开头的，模13为k的数的统计情况，其中 c 可取0或者1，0表示不包含13，1表示包含，这样我们就可以把所有的数分成两部分，设计状态转移方程。 1、状态转移方程： dp[i][j][...
动态规划——数位dp入门（二）
对数字整体进行考虑的处理方法 较为简单的数位dp只会涉及到每一位上的数字变化，如比较相邻数字差，是否含有某个数字等等，在这种情况下一般用dp【i】【j】就可以，i表示数字长度，j用来表示首位数字。如果题目要求对数字整体进行考虑，我们不能对各个位置上的数直接判断，就需要对每位之前判断过的数进行记忆化存...
动态规划学习系列——区间DP（一）
学习一个算法，还是从题目开始比较好，我们就从一道经典例题开始： wikioi 1048 石子归并 Description 有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并...
动态规划_数位DP
数位DP的一般思路当计算一个很大的数中，符合条件的数有多少种，一般采取数位DP的方式去解决该问题。作为模板，我采用了记忆华搜索的方法。 解题思路 代码框架 例题1 HDU 2089（简单） 例题2 HDU 4507（适中） 解题思路对于这类问题，我们将考虑数字每位上的情况。 对于数字...
动态规划学习系列——数位DP（练手四）
题目链接：hihoCoder 1033 解题思路： 思路超级简单，就是单纯的数位DP，但是，还是觉得好恶心。需要特殊考虑的就是第一位数字为0的情况，不能直接把状态转移的结果拿出来。 状态：dp[i][j][k+100]，i 位数中以 j 开头的数交叉和为k的数量 （这里因为k有可能取负数...
动态规划学习系列——区间DP（二）
上一篇我们看了区间型DP的一道经典入门题——石子归并，这一次同样是类似的一道题——石子归并2 题目链接：wikioi 2102 题干不同之处在于，现在我们的石子不是排成一列了，而是围成一个环，我们要怎么把问题转化成普通的石子归并呢？ 其实这是一种挺常见的算法技巧——变环为列 方法：长度为le...
动态规划学习系列——划分DP（三）
划分DP第三题，wikioi 1040，送我n个WA~~~ 题目大意： 这道题题述有着UVA的特色，够废话，其实就是读入一个长度最大200的字符串（不知道为何要分行输入，完全没有意义啊），分成m部分，使各部分单词量加起来最大 解题思路： 这题划分的部分跟乘积最大那题其实很像，状态转移方程也很容...
动态规划——数位dp
通过先前在《动态规划——背包问题》中关于动态规划的初探，我们其实可以看到，动态规划其实不是像凸包、扩展欧几里得等是具体的算法，而是一种在解决问题中决策的思想。在不同的题目中，我们都需要根据题设恰到好处的把整个过程分割成小的状态，然后找到对应的状态转移方程，尽管都是这个过程，但是有时候条件稍微一遍...
dp 动态规划 hdu 1003 1087
动态规划就是寻找最优解的过程最重要的是找到关系式hdu 1003题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003题目大意：求最大字序列和,其实就是分成以0结尾的序列以1结尾的序列以2结尾的序列...以n结尾的序列所以以n结尾的序列的最大值就是以n...
【Pytorch】第 2 章 ：马尔可夫决策过程和动态规划
????大家好，我是Sonhhxg_柒，希望你看完之后，能对你有所帮助，不足请指正！共同学习交流???? ????个人主页－Sonhhxg_柒的博客_CSDN博客 ???? ????欢迎各位→点赞???? + 收藏⭐️ + 留言???? ????系列专栏 - 机器学习【ML】 ...
POJ 2342 Anniversary party / HDU 1520 Anniversary party / URAL 1039 Anniversary party（树型动态规划）
POJ 2342 Anniversary party / HDU 1520 Anniversary party / URAL 1039 Anniversary party（树型动态规划）DescriptionThere is going to be a party to celebrate the ...
hdu 1176 免费馅饼(动态规划)
AC code:#include<stdio.h>#include<string.h>#define max(a,b) (a>b?a:b)#define maxof3(a,b,c) (max(max(a,b),c))int dp[100005][12];int main...
【暑假】[深入动态规划]UVa 10618 Fixing the Great Wall
UVa 10618 Fixing the Great Wall题目： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36139思路： 数轴上有n个点需要修复，每个点有信息c,x,d 表示位于x且在t时修缮的费用是c+d*t，...
WeetCode3 暴力递归->记忆化搜索->动态规划
笔者这里总结的是一种套路，这种套路笔者最先是从左程云的b站视频学习到的本文进行简单总结系列文章目录和关于我一丶动态规划的思想使用dp数组记录之前状态计算的最佳结果，找出当前状态和之前状态的关系（状态转移方程）然后使用状态转移方程，计算处当前状态最佳结果，然后更新dp数组，填完dp数组即得到最佳结果本...
BZOJ_1609_[Usaco2008_Feb]_Eating_Together_麻烦的聚餐_(动态规划,LIS)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=1609给出一串由1,2,3组成的数,求最少需要改动多少个数,使其成为不降或不升序列.分析法1:改动一些数字后变为不升(不降)序列,那么除了需要改动的数字以外,其他的数字本身满足不升(不降),所以求最...
切割钢条-动态规划
问题 C[J] ：以J为长度的钢条的最佳切割收益。子结构：C[J]=MAX{P[J],C[J-I]+P[I]} 一个钢条的最佳收益：假设至多一刀，要么切，要么不切，遍历所有情况，找出最大的收益情况（P[J];不切，C[J-I]+P[I] ： 在I位置切一刀）初始化：C[0]=0；追踪：r...