[综合] caioj 1084 动态规划入门（非常规DP8：任务安排）（取消后效性）

这道题的难点在于，前面分组的时间会影响到后面的结果也就是有后效性，这样是不能用dp的所以我们要想办法取消后效性那么，我们就可以把影响加上去，也就是当前这一组加上了s那么就把s对后面的影响全部加上这个做法非常巧妙。 #include<cstdio> #include<algorith...

[综合] 洛谷P1280 caioj 1085 动态规划入门（非常规DP9：尼克的任务）

这道题我一直按照往常的思路想f[i]为前i个任务的最大空暇时间然后想不出来怎么做……后来看了题解发现这里设的状态是时间，不是任务自己思维还是太局限了，题做得太少。 很多网上题解都反着做，那么麻烦干嘛 设f[i]为前i时间内的最大空暇时间。这里是更新后来的状态，和以前不一样。如果i为某个任务的开始时间...

[综合] caioj 1087 动态规划入门（非常规DP11：潜水员）(二维背包)

这道题的难点在于价值可以多。这道题我一开始用的是前面的状态推现在的状态实现比较麻烦，因为价值可以多，所以就设最大价值为题目给的最大价值乘以10 #include<cstdio> #include<algorithm> #include<cstring> #defi...

[综合] caioj 1086 动态规划入门（非常规DP10：进攻策略）

一开始看到题目感觉很难然后看到题解感觉这题贼简单，我好像想复杂了就算出每一行最少的资源（完全背包+二分）然后就枚举就好了。 #include<cstdio> #include<algorithm> #include<cstring> #defineREP(i,a,...

[综合] 洛谷P1164 小A点菜 caioj 1410 动态规划1：点菜（背包方案问题）

方程很简单 f[0]=1 f[j]+=f[j-w[i]] #include<cstdio> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constintMAXM=11234; constintMAXN=112...

[综合] Vijos 1071 caioj 1411 动态规划2：打牌 （背包方案输出）

非常奇怪的是，我在Vijos1071能AC，在caioj就只有50分 可以和前面一道题一样算方案，如果大于1就是多解 然后就输出方案就好了 #include<cstdio> #include<cstring> #defineREP(i,a,b)for(inti=(a);i&l...

[综合] caioj 1412 动态规划3：a+b问题(完全背包方案数)

每个素数就是一个物品，然后就相当于求完全背包方案数 把max改成+就好了。 #include<cstdio> #include<vector> #include<cstring> #defineREP(i,a,b)for(inti=(a);i<(b);i++...

[综合] caioj 1413 动态规划4：打鼹鼠

记住一定要区分n和m分别代表什么，我已经因为这个两道题浪费很多时间了然后这个道题有点类似最长上升子序列n平方的做法，只是判断的条件不同而已 #include<cstdio> #include<algorithm> #include<cmath> #defineRE...

[综合] 洛谷P2196 caioj 1415 动态规划6：挖地雷

没看出来动规怎么做，看到n<=20,直接一波暴搜，过了。 #include<cstdio> #include<cstring> #include<algorithm> #defineREP(i,a,b)for(inti=(a);i<(b);i++) u...

[综合] 洛谷 P1156 垃圾陷阱 （01背包拓展）（好题！！）

这真是一道好题目 学到了很多 一开始感觉吃或者不吃会有后效性 然后看到洛谷的题解，直接把这个有后效性的部分当作dp的维度和值 因为这个垃圾可以堆或者不堆，所以这个很像01背包，但是加了非常多的限制条件，是一个升级版的01背包 记住思考01背包问题的时候，要思考i那一维度，最后再考虑要不要用滚动数组...

[综合] 洛谷P1108 低价购买 （最长下降子序列方案数）（int，long long等 范围）

这道题用n方的算法会很好做 我一开始想的是nlogn的算法求方案数，然后没有什么想法（实际上也可以做，但是我太弱了）我们就可以根据转移方程来推方案数，只是把max改成加，很多动规题都是这样，比如背包的方案数。设f[i]为以i为结尾的方案数当b[j]+1==b[i]且a[j]>a[i]时，f[i...

[综合] caioj 1618 【动态规划】矩阵相乘的次数

刷刷水题压压惊 低级版的能量项链 相当于复习一次中链式dp 这种合并了之后又后效性的题目 都可以用类似的方法做 #include<cstdio> #include<cstring> #include<algorithm> #defineREP(i,a,b)for(...

[综合] caioj 1106 树形动态规划（TreeDP）1：加分二叉树

解这道题的前提是非常熟悉中序遍历的方式我就是因为不熟悉而没有做出来中序遍历是571210的话，如果1是根节点那么571就是1的左子树，2，10就是右子树这就有点中链式dp的味道了，实际解法也是中链式dp的解法设f[i][j]为中序遍历从i到j的最大价值f[l][r]=f[l][mid-1]*f[mi...

[综合] 洛谷 P2015 二叉苹果树 caioj1107 树形动态规划（TreeDP）2：二叉苹果树

这道题一开始是按照caioj上面的方法写的（1）存储二叉树用结构体，记录左儿子和右儿子（2）把边上的权值转化到点上，离根远的点上（3）用记忆化搜索，枚举左右节点分别有多少个点，去递归 这种写法有个好处，避免了总的树枝个数的枚举 #include<cstdio> #include<a...

[综合] caioj 1112 树形动态规划（TreeDP）7：战略游戏

这道题和上一道题非常相似 这道题是看边，上一道是看点。 但是状态定义不同 看边的话没有不放不安全这种状态 因为当前结点的父亲无法让这颗子树没有看到的边看到 所以这种状态不存在 而上一道题存在不放不安全这种状态 因为当前结点的父亲可以让这个不安全的结点变得安全 边和点是两种不同的思考方式，得出得状态和...

[综合] 1113: [视频]树形动态规划（TreeDP）8：树（tree）(树形dp状态设计总结)

根据最近做的几道树形dp题总结一下规律。（从这篇往前到洛谷P1352）这几道题都是在一颗树上，然后要让整棵树的节点或边满足一种状态。然后点可以影响到相邻点的这种状态然后求最小次数 那么要从两个维度来设计状态第一个维度（1）以i为根的树的所有节点都满足这种状态（2）以i为根的树的只有i不满足这种状态第...

[综合] caioj 1114 树形动态规划（TreeDP）3.0：多叉苹果树【scy改编ural1018二叉苹果树】

一波树上背包秒杀…… #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #defineREP(i,a,b)for(inti=(a);i<(b);i++)...

[综合] 洛谷 P1282 多米诺骨牌

这道题很有收获。 我自己想的时候有想到这是一个背包，但是写的实现非常麻烦，还是错的。 我想的是在背包的过程中尽量靠近0，但是这样显然有后效性而且我思考背包的方式不对。要考虑当前物品有哪几种可能，然后比如这道题就是交换或者不交换。先用二维的思考方式，滚动数组只是后面的优化。 后来看了题解，很有收获 ...

[综合] 洛谷 P1417 烹调方案 （01背包拓展）

一看到这道题就是01背包 但是我注意到价值和当前的时间有关。 没有想太多，直接写，0分 然后发现输入方式不对…… 改了之后只有25分 我知道wa是因为时间会影响价值，但不知道怎么做。 后来看了题解，发现我对01背包理解不够透彻普通01背包做下来放入物品的顺序是1到n的因为这个时候顺序没有关系，所以可...

[综合] 洛谷 P1855 榨取kkksc03 （二维费用背包）

加多一维就行了 #include<cstdio> #include<algorithm> #include<cstring> #defineREP(i,a,b)for(inti=(a);i<(b);i++) #define_for(i,a,b)for(int...