hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

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

[JSOI2015]地铁线路来自专栏

题意：有n个站点，m条路线，每条路线使用一次要交1块钱，给出每条路线的信息，从一个站点到下一个站点的时间为1，让你求从一个站点到另一个站点的最小花费是多少，此时花费时间最大为多少？思路：最短路+拓扑+dp一看就是图论题，第一问求最小花费，如何用最短路求呢，对于每一条路线我们要创建两个虚点，一个虚点...

最短路 dp

2021-04-21

2 895

[HAOI2012]音量调节来自专栏

题意：有一个歌手要唱n首歌，每首歌在唱之前可以调节ci的音量,上调或者下调，但不能低于0或者高于maxLevel，初始音量为beginLevel，求最后一首歌音量最大为多少，如果不能满足规则，则输出-1. 思路：首先观察数据范围，我们发现n和maxLevel都不是很大，所有我们可以使用dp来写. 定...

dp

2021-04-19

4 869

Dima and Salad 来自专栏

题意：给出n个物品的ai和bi的值，求在满足所选物品ai之和除以bi之和等于k时ai之和最大为多少？思路：将每一个物品的ai看成价值，ai-bi*k看成体积，这样题目就变成了所选物品体积为0时价值最大为多少？给体积一开始就加上一个较大的值来解决下标为负的问题，这样就只是一个简单的01背包问题了。 ...

dp

2021-02-10

1 608

Subsequences (hard version) 来自专栏

题意：给出一个长度为n的字符串和一个k，求形成k个不同子串组成的集合至少要删除多少字符？如果无法完成则输出-1. 思路：动态规划：dp[i][j]表示前i个字符组成一个长度为j的不同子串的数目；dp[i][j]=dp[i-1][j] (不加第i个字符)+dp[i-1][j-1] (加第i个字符)+d...

dp

2021-02-10

1 524

Bookshelves 来自专栏

题意：给你一个长度为n的数组，请你按顺序分成k份，然后将每一份的和进行位与操作，求结果最大为多少？思路：从高位到低位枚举结果，即如果加入该位后结果满足条件则将该位加入结果，否则舍弃该位。判断结果是否满足条件使用dp：dp[i][j]表示将前i个数分成j组是否满足条件；dp[i][j]=(dp[i]...

位操作 dp

2020-11-17

3 703

Mr. Kitayuta, the Treasure Hunter

题意：有一个由30001个小岛组成的群岛，编号为0-30000，一字排开，首先从0岛跳的d岛，然后每一次跳的距离与上一次的距离绝对值等于小于1，有些岛有宝石。思路：dp:ma[i]表示i岛的宝石数目。dp[i][j]表示跳到i时跳的距离为250-j+d时收集的最大宝石数。初始化dp[d][250]...

dp

2020-08-27

1 537

购物

题意：有一家糖果店，每天可以生产m颗糖果，你在接下来n天会去买糖果，你每天必须吃一颗糖果，你买的糖果可以保存以后吃，你每天买糖果还需要额外花当天买的糖果个数的平方的钱，求这n天你最少花多少钱？思路：dpdp[i][j]表示前i天买j颗糖果的最少花费。sum[i][o]表示第i天买o颗糖果的糖果花费...

dp

2020-08-09

1 690

Max Power

题意：有一颗n层的技能树，第i层有n-i+1个技能,学习第i层第j个技能则必须先学习第i-1层第i和i+1个技能，第一层的技能可以直接学。你能学m个技能，求你最大的战力加成为多少？思路：dp我们发现如果第i层第j个技能学习了，则以它为底的倒三角的技能一定学习了。设dp[i][j][r]为第n列到第...

dp

2020-08-07

1 652

[CQOI2007]涂色PAINT

题意：让你对n个长度的木板染色，每次可以对连续的任意长度染同一种颜色，初始没有颜色，求最少需要染多少次能染成目标颜色？思路：区间dpdp[i][j]表示从i到j的区间染成目标颜色的最少染色次数。当第i个格子和第j个格子的颜色相同时，第i个格子可以被dp[i+1][j]顺便染成、第j个格子可以被dp...

dp

2020-08-02

1 811

乌龟棋

题意：有一个长度为n的一维数组，每个元素有一个分值，你一开始在第一个元素的位置（1），你有m张卡片，有1，2，3，4四种类型，使用卡片可以让你移动等价于卡片数值的格数，然后将移动后到达位置的分值加上，求最大分值为多少？（使用完所以卡片后一定到位置n）思路：像这种类型的题九成用dp，做dp题你需要考...

dp

2020-08-02

1 850