在刷题的单身狗很开心 - 个人主页动态 - 牛客网

发布(192) 评论刷题收藏

2023-10-15 15:36

中原工学院 Java

题解 | #合并回文子串#

字符串c中价值最大的子串一定是由A中的某个子串和B中的某个子串组成的。 那么对于已知的dp[i][j][k][l]的状态，可以转移到取A字符串两边放到C字符串两边。 可以是取B字符串两边放到C字符串两边。 可以是取A字符串的右边和B字符串的左边来放到C字符串的两边 可以是取A字符串左边和B字符串的右边来放到C字符串的两边。 那么状态转移方程为： // if (a[i]==a[j]) dp[i][j][k][l] |= dp[i+1][j-1][k][l]; // if (b[k]==b[l]) dp[i][j][k][l] |= dp[i][j][k+1][l-1]; // if (a[i]=...

0 点赞评论收藏

分享

2023-10-14 10:26

中原工学院 Java

题解 | #田忌赛马#

本题首先看上去像是一个贪心问题，对于齐王的马从大到小进行排序，然后对于齐王的马来说如果田的马没有比齐王马好的，那么就使用田最弱的马和他去比。如果有比齐王好的马就 去赢。 但在这里面有反例的存在，如果平局的时候怎么办？是直接平局好还是输掉好？例如：1 2 3,1 2 3来说算平局就是0，那么就没有输掉的效果好。例如：田：2 3，齐：1 3。如果算输的话就是0。但如果算平的话就是200。所以在平局的时候策略并不是唯一的。 在这里我们观察，田从齐王最大的那匹马开始，田无非就是上第一匹或者上最后一匹马那么也就是说选第一或最后一个两个选后最大的那一个。 那么dp[i][j]表示i到j这...

0 点赞评论收藏

分享

2023-10-13 21:02

中原工学院 Java

题解 | #凸多边形的划分#

本题凸多边形要划分成三角形可以从定点和定边两个角度来看，从定点角度来看的话定一个点后，后两个点再去分隔所形成的的三个多边形并不是连续的区间。这样的话对于区间dp来说不好处理。 但是从定边这个角度来看的话，定一条边后去选取另外一个点这样形成的一个区域一定是一个三角形，另外两个区域一定是一个连续的区间，那么我们将0,1作为选取的边来看的话也就解决了圈的问题。 所以在这里可以将动态规划转移方程：dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);。 本题的数据过大，得使用int128，这是个比较坑的点。 #inc...

0 点赞评论收藏

分享

2023-10-12 22:12

中原工学院 Java

题解 | #石子合并#

本题针对于区间进行操作，是一个区间dp的问题。对于某个区间i,j能够得到的最大值等于在区间里面分成两部分中所有两部分的最大值。那么再看分出来的这两部分其实又可以划分两部分。 那么动态规划的状态转移方程就出来了：dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]+sum[i][j]);。 最后以最短的区间来世初步动态规划边长就行。 至于圈这个特殊性，可以使用加倍的方式来代替，也就是在数列后面接上一个重复的数列，这样转一圈之后回来就可以表示出来了。 #include <bits/stdc++.h> using&n...

0 点赞评论收藏

分享

2023-10-11 21:55

中原工学院 Java

题解|#「木」迷雾森林#

某一个位置上的途径数其实源于左边和下面，也就是说某一个位置只来自左边和下边。那么动态方程就可以出来了。 又有可以使用BFS来走这个地图所以在BFS的过程中加入动态规划记录累计的途径数就可以了。 #include <bits/stdc++.h> using namespace std; int read() {     int ans=0, k = 1;     char ch =...

0 点赞评论收藏

分享

2023-10-11 20:06

中原工学院 Java

题解 | #钉子和小球#

本题动态规划问题的状态转移很明显在小球下落的每一层里面发生变化，所以使用二维dp[i][j]来表示某一行某一个钉子或者去掉的钉子所拥有的小球。 题目要求最后以分数的方式给出答案，那么我们可以以小球的数量比下手，小球每进过一次钉子就会分裂成两个，这样就去考虑他到达底部某个槽子里面有多少个小球，然后除于到达底部的全部小球就是最后要的结果。 那么对于去掉钉子的地方呢，去掉钉子的地方会直接性的下落两层，那么就业是说直接给下落两层的地方的数量变成该地方乘四即可。 #include <bits/stdc++.h> using namespace&nbsp...

0 点赞评论收藏

分享

2023-10-10 23:16

中原工学院 Java

题解 | #免费馅饼#

动态规划问题，用时间和水平方向的编号作为一个二维的状态。那么某个时间下某个水平编号所能够得到的最大的分数就是由上一个时间段的状态通过5种移动方式得到的。那么状态转移方程就出来了。因为没有涉及到的编号不存在所谓的转移，所以一开始将数组初始化成-1，判断如果等于-1的话直接跳过。 对于路径：同样通过倒索引的方式去一步一步寻找输出。 #include <bits/stdc++.h> using namespace std; // #define int long long struct Oper{...

0 点赞评论收藏

分享

2023-10-10 16:41

中原工学院 Java

题解|#花店橱窗#

是一个动态规划问题，不是背包问题，背包问题的特点在于有最优的值，而且有某种限制。在这里面需要将花插入花瓶当中，由于有所有的花束在放入花瓶时必须保持其标识数的顺序这个限制。所以应该最外层是以花作为遍历，这样可以保证这个顺序。 那么动态转移方程为：dp[i][j]=max(dp[i-1][1~j-1])+val[i][j];。 关于方案如何给出，在这里采用向前一个去寻找的方式，也就是记录当前i，j下是由上一个哪个转移过来的。这样只要找到最优的那一个向上去寻找，将路径保存进栈里面最后将栈输出即可。 #include <bits/stdc++.h> usi...

0 点赞评论收藏

分享

2023-10-10 11:42

中原工学院 Java

题解|#可爱の星空#

对于某个数量的星星来说，它的连同的最小代价应该是将其折半后拼接，那么折半后折半下来的其余部分也按照这样折半的思路去，之后全部相加就是最小的代价。 //以星星为第一维，那么每加入一个星星能够得到的代价作为二维。 #include <bits/stdc++.h> using namespace std; #define int long long int dfs(int depth) {     if (depth==0) retu...

0 点赞评论收藏

分享

2023-10-09 22:20

中原工学院 Java

题解 | #草药大师#

题目需要对dp进行优化来减少不需要的空间和时间，在这里我们使用map去保存，使用滚动数组去代替每一种草药。 那么某一种草药对状态的影响就可以表示为去遍历map里面的每一个元素，拿这个元素的时间去加上这个时间，如果满足条件那么就可以去判断这将it->first+t这个时间下的最大值更新掉。 这样可以避免需要不必要的空间。 #include <bits/stdc++.h> using namespace std; #define int long long map<int, int&gt...

0 点赞评论收藏

分享

2023-10-09 21:36

中原工学院 Java

题解 | #队伍配置#

本题从者和装备都只能使用一次，证明是一个01背包问题。但是条件中对于装备又受从者的限制，从者也最多只能有5个。除此之外还有cost值的限制。再加上每一个装备或者从者本身都就有4个东西需要去维护了。而对于装备或者从者本身可以使用滚动数组的方式不需要去创建一个数组维度。 那么本题中装备的维度必须在从者之后，因为能够装多少件装备是由从者去决定的，对于cost值来说放前放后到时都行。 在这里dp[i][j][k]。其中i表示cost值，j表示从者数量，k表示装备数量。总体代表在在这些条件下的最大ATK值。 那么在某个cost下装备的数值其实取决于从者的数值，所以先计算出从者的最大AT...

0 点赞评论收藏

分享

2023-10-08 22:56

中原工学院 Java

题解 | #[NOIP2006]金明的预算方案#

又看错题了。。。。。题目中所说的意思是一个一个主件最多能够有2个附件，这是在给数据的时候规定好的不是我们去控制的。所以在某种主件下最多就只有4中情况。 那么将这四种情况枚举出来，那么就和分组背包是一模一样的问题了。 分组背包：将组作为对外层循环，这样对于每个组选取哪一个就只和之前的那一组有关了，所以可以将当前组的所有物品都遍历一遍，那么他们在某个价值下的最大值要么是取当前要么不取。 那么使用滚动数组就可以让这个取与不取在内部遍历的时候就取到最大值。 //分组的背包问题，但是与雨巨演示的不同在于不同组有不同的选取数量。 #include <bits/stdc...

0 点赞评论收藏

分享

2023-10-08 21:27

中原工学院 Java

题解 | #多重背包#

首先可以将多重背包的每一种物品的数量都看做一种物品，这样就转化成了01背包。但是由于数据过大会超时。 所以在这里采用二进制的优化，可以使用二进制将其某种物品的数量捆绑成1,2,4,8.。。。。。。这样可以将表示的数量缩短。 然后采用01背包的做法即可。 #include <bits/stdc++.h> using namespace std; struct Node{     int weight;     int val...

0 点赞评论收藏

分享

2023-10-08 16:42

中原工学院 Java

题解 | #[NOIP2018]货币系统#

本题是一个完全背包问题，但需要将题目中的问题进行转换。题目中要求最小的等价货币系统的m值。那么其实就是求原有的货币序列里面有哪些数是可以被其他数表示出来的，那么这些数就是不必要存在的数。又有肯定是小的数可以组合成大的数，所以可以首先对序列进行一个排序。 然后对于数的排除其实就相当于某个数可以用无数次，求这些数可以组成的数。这就和完全背包很像了吧，那么我们建立一个一维dp，用来表示在某个数下能够组成的数，能的话是1不能是0所以初始全部复制成0，对于0赋值成1。然后当前的数能否组成j这个数一方面取决于之前的数能否如果另一方面取决于j-a[i]在之前能否组成。那么递推式就出来了。每次判断这个数...

0 点赞评论收藏

分享

2023-10-08 11:47

中原工学院 Java

题解 | #Steadily Growing Steam#

这题和失衡天平 (nowcoder.com)这道题很像，都是天平两端需要放东西，那么就把必然需要去维护一个天平两端重量差。但是这道题还有一个技能的使用，使用技能可以将点数加倍。所以这个技能的使用也得需要维护。那么就是维护一个技能的使用次数。 //将手上的牌分成两部分，如果两部分点数相同那么就得到这两部分的牌。 在开始之前还可以全选一些牌将其点数增加二倍。最后要value最大的方式。 状态转移一共有五种情况： 1、不选当前的卡片：dp[i][j][k] = dp[i-1][i][j]; 2、选当前的卡片但将其放到点数大的那一个里面(不使用技能)：dp[i][j][k] = max(dp[i...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务