Phecda_

分类

未归档(109)

/ 注册

全部文章（共13篇）

LuoGu P1004 方格取数

题目传送门一开始这个题我是不会的(沙华弱DP啊QwQ)，后来考完试我一想，这东西怎么和数字三角形那题这么像啊？都是自上而下，只能向下或者向右，求一个max 那么...这不就是个走两遍的数字矩阵嘛转移方向都没换:对于(i,j)，只能由(i-1,j)或(i,j-1)转移过来转移解决了，那...

DP 网络流

2018-09-06

0 529

LuoGu P1006 传纸条

题目传送门这题嘛...方格取数和这题一样一样的只不过这题是从左上到右下再回去罢了（来回一趟和来两趟有区别么？没有，那么这题和上题用一样的转移和状态就行了没什么好说的，说一下我的错误好了：人家图是nm的，我给存成了nn的（即使这样还是得了60分）读入对了后，转移的时候又成了n*n的...

DP

2018-09-06

0 329

LuoGu P1541 乌龟棋

题目传送门乌龟棋我并不知道他为啥是个绿题0.0 总之感觉思维含量确实不太高（虽然我弱DP）（毛多弱火，体大弱门，肥胖弱菊，骑士弱梯，入侵**，沙华弱Dp）总之，设计出来状态这题就很简单了设 f[i][j][k][l] 表示第一种卡片用了 i 张，第二种用了 j 张，以此类推就好了（我太懒了啦）...

DP

2018-09-11

0 533

LuoGu P1352 没有上司的舞会

题目传送门这可能是最简单的树形Dp了吧对于每个人，要么他来，他的下属不来要么他不来，他的下属爱来不来于是设计状态： f[i][0/1]表示以i为根的子树中最大能达到的快乐值(i这个人选或者不选) 然后一遍dfs一遍转移就好了 #include <iostream> #inclu...

DP

2018-09-11

0 351

清北-Day6-regular

题目描述给出一个只包含左括号和右括号的字符串，插入若干左右括号（可以插在任意位置）之后使得字符串长度为$ 2\times n $ 且是一个合法的括号序列。求最后能组成多少种不同的合法括号序列。【合法的括号序列：该序列任意一个前缀的左括号数大于等于右括号数,最终左括号数等于右括号数】输入输入...

DP

2018-11-05

0 379

LuoGu P4996 咕咕咕

题目描述小 F 是一个能鸽善鹉的同学，他经常把事情拖到最后一天才去做，导致他的某些日子总是非常匆忙。比如，时间回溯到了 2018 年 11 月 3 日。小 F 望着自己的任务清单：看 iG 夺冠；补月赛题的锅。小 F 虽然经常咕咕咕，但他完成任务也是很厉害的，他一次性可以完成剩余任务的...

组合计数 DP

2018-11-05

0 276

CodeForces1204C

CodeForces1204C 其实我觉得这是一道比较综合的题吧... 这个题可供挖掘的性质很多,比如最短路最长是\(n\)啊,答案序列中的两点之间的距离肯定是\(p\)数组上这两个点的距离啊等等. 其实是在\(p\)数组上进行了一次另类的最短子序列.图的条件其实就是限制了转移,然后再有一个有点意...

最短路 DP CodeForces

2019-08-23

0 434

CodeForces1154F

CodeForces1154F \(ZS\)大佬说这是一道\(SBDP\)题.然鹅我懵逼了半天才懵逼过来怎么做(还是在\(solution\)和\(ZS\)大佬的指导下才明白...) 数据范围疯狂暗示你\(O(k^2)DP\),事实上稍微一想状态就出来了,\(f[i]\)表示买\(k\)双鞋的最少花...

DP 前缀和 CodeForces

2019-08-26

0 455

TLS 9.2C

TLS 9.2C 这个题目我觉得我做的\(50\)分做法比\(100\)分的\(SBDP\)更具有价值. 因为这个\(DP\)真的很简单. 令\(f_{i,j}\)表示以\((i,j)\)为右下角的最大正方形的边长.则有转移方程: \[f_{i,j} = min ( f_{i-1,j-1}...

悬线法 DP

2019-09-02

0 438

ZROI#1005

ZROI#1005 非常令人迷惑的一个题... 首先,我们发现,那个$M$并没有什么卵用. 于是我们直接不鸟它. 然后我们发现我们需要找一个最小的糖浆的集合$S$. 使得下式成立: \(\sum_{i\in S}{k_i*v_i}=N\) 其中$k_i$表示第$i$种糖浆选了几份,$v_i$表示糖...

DP 最短路背包

2019-09-23

0 389