Z_L_G

题解

总结(20) 训练赛(18)

/ 注册

全部文章 / 题解（共129篇）

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

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

dp 完全背包

2025-07-08

0 38

算法入门-[SCOI2009]粉刷匠

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

dp 多次dp

2025-07-08

0 33

脑洞大开-打砖块(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 36

算法入门-Min酱要旅行

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

多次dp 01背包

2025-07-07

0 43

算法入门-Mondriaan's Dream

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

状压dp 妙妙题

2025-07-05

0 29

算法入门-[NOIP2008]传纸条

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

双线dp

2025-07-05

0 35

算法入门-Most Powerful

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

状压dp

2025-07-03

0 40

算法入门-炮兵阵地

题意给定N*M的地图，包含山地和平地，山地不能布置炮兵炮兵会攻击自己上下两格，左右两格的位置，请问在炮兵相互不打架的情况下，地图上最多放置多少炮兵思路仍旧按行考虑，预处理行内可行状态枚举每行可能性，和前两行状态有关，所以是一个三维的dp 表示第i行状态j，i-1行状态为k 代码 ...

状压dp

2025-07-02

0 33

算法入门-[SCOI2005]互不侵犯KING

题意有一个N*N(N<10)的棋盘，其中需要放置K个国王，国王会攻击以他为中心的九宫格范围内的棋子，要是所有国王互不攻击，总共有多少种方案思路如果按顺序从上到下，从左到右，每次放置新的国王的时候都需要考虑它左边和上侧的国王，状态过于复杂难以描述由于N不大可以考虑一行一行放置，这样...

状压dp

2025-07-02

0 51

算法入门-小A买彩票

题意买彩票，3元一张，中1,2,3,4元的概率相等买n张，求不亏的概率输出要求：最简分数，如果概率为0就输出"0/1"，概率为1就输出"1/1" 思路类似昨天弹球的问题状态转移可以靠钱勾连表示买了i张彩票赚j元的可能最后求一个GCD就行，注意只要买了就会亏，所以概率为1只有可能...

dp 概率

2025-06-28

0 37