Z_L_G

分类

总结(20) 训练赛(18) 题解(129)

/ 注册

全部文章（共165篇）

算法入门-[NOIP2018]货币系统

#动态规划 #完全背包题意给定一个n种面值组成的货币系统，如果其中某一个面值可以由系统中的其它货币表示就认为这个面值是冗余的求出这个货币系统去除冗余后最少有几种面值思路按照题意完全背包即可注意判断一个货币是否冗余，是在使用它之前判断是否已经被表示代码 #include<b...

dp 完全背包

2025-07-08

0 34

算法入门-[SCOI2009]粉刷匠

#动态规划 #多次dp 题意有n块木板，每块木板有m格，你可以粉刷t次，每次可以粉刷连续的若干格，不能覆盖给定正确的粉刷方案，请问最多可以刷对多少格 0<=n,m<=50,t<=2500 思路如果只有一块木板，可以线性dp解决表示刷i次，刷到j 对于若干块板子，如果...

dp 多次dp

2025-07-08

0 32

脑洞大开-打砖块(brike)

#妙妙题 #动态规划题意倒置金字塔形的砖块墙，共有n行，第i行有n-i+1块砖每块砖有价值，敲掉一块砖需要敲掉它左上和右上的两块砖敲掉m块砖能获得的最大价值总和是多少 n<=50,m<=500 思路原数据读入形式如下 1 2 3 4 5 1 2 3 4 1 2 3...

妙妙题 dp

2025-07-08

0 31

算法入门-Min酱要旅行

题意有k个物品，每个物品有体积，求空间为1~m，不带第1~k件的方案数思路无法考虑枚举不带某一个物品，对剩下的物品01背包，复杂度直接爆炸反向思考，可以求解k个物品装满m空间的01背包(每个物品用一次，恰好装满指定体积)，然后再减去必须取某一个物品装满m空间的方案数，就得到去掉某一个物...

多次dp 01背包

2025-07-07

0 36

最大全0子矩形问题

题意对于一个由0,1构成的矩形，求解其中面积最大的全0子矩形，和全0子正方形思路法一：枚举上下左右四个边界，利用二维前缀和，如果前缀和为0就成立复杂度：法二：枚举左右边界，对边界内的1按y排序，每两个相邻点+边界构成矩形复杂度：,(m为1的个数，最多到) 法三：悬线法，...

dp

2025-07-06

0 28

状压dp

什么是状压对于题目中一种复杂的状态，如多维，多行，多条路，某种方案，某种集合等压缩成一个整数的过程就是状态压缩这也可以看作是一个Hash的过程除去压缩状态的过程，其实它整体和普通的dp差别不大，都是从已知过程推向位置过程压缩的意义在于把一个一般无法描述的状态，变成一个包含多种信息的状态，而...

状压dp

2025-07-06

0 35

算法入门-Mondriaan's Dream

题意 n行m列矩形，用1*2的矩形块填充，有多少种填充方案思路依然是棋盘放置一类的问题，考虑一行一行放对于每一行，上一行竖着放的地方一定放不了，上一行横着放的地方可以竖着放也可以横着放，行内不可能的是把一个横着的拆开，两行间不可能的是，上一行竖着，这一行还放东西设计状态：横着放记为0，...

状压dp 妙妙题

2025-07-05

0 27

算法入门-[NOIP2008]传纸条

#双线dp 双线表示同时有两种状态，且会相互影响题意给定M*N的地图，每个点有val，每个点只能走一次从左上走到右下再走回左上，且向下的过程只能向下向右，向上的过程只能向上向左走完最多获得的val是多少思路思路一：严格按照一圈走无法完成，走下去的过程走过的格子会影响走上去的过程...

双线dp

2025-07-05

0 30

算法入门-Most Powerful

题意 n个原子，两个原子i，j碰撞会释放能量，并且j会消失，求n个原子能产生的最大能量思路状压dp 每个原子去碰撞的时候，要还剩下哪些原子也就是每次从还存在的原子中挑出两个原子碰撞，并选择一个消失最终剩下一个原子结束状态压缩是你过程，从全满，到只剩一个特别的，在st=0的时候要人为...

状压dp

2025-07-03

0 35

TSP问题

题意旅行商问题，在一个若干点的图中，设计一条最短路径，途径所有点有时最终会要求回到原点思路状压dp 访问每一个点的时候需要考虑当前已经访问了哪些点走到某一个点的最短路径应该是所有(上一步最短路径+上一步所在点到当前点距离)取最小表示当前状态为st，最后一个点时i的最短路径代码...

状压dp

2025-07-03

0 31