江三

分类

题解(25)

/ 注册

全部文章（共25篇）

每日一题乌龟棋 (记忆化搜索)

一.题意 n个格子，1为起点，n为终点每个格子有一个分数每个格子有一个分数有 4 种卡片，分别为1，2，3，4，代表能走的步数走到一点得到该点分数所有卡片相加恰好到 n 点求最大能得到的分数二.题解四种卡片用完恰好到达终点，而使分数不同的因素是卡片的使用顺序不难联想到全排列加上数据比较小可以考虑...

每日一题记忆化搜索

2020-07-24

0 619

每日一题小A的柱状图 (单调栈)

一.题意给出 n 个小长方形的宽度和高度，求最大的矩形面积。二.题解先谈谈经典的单调栈模板题的解法，给出高度且宽度恒为1，求最大的矩形面积。用单调栈维护每个点左边第一个比自己矮的矩形和右边第一个比自己矮的矩形，得到 r 数组和 l 数组。那么 ~ 之间的矩形中最矮的就是，即以当前矩形为最...

单调栈每日一题

2020-07-23

0 554

每日一题 wpy的请求 (spfa)

一.题意给出 n 个点和 m条边的有向图，边权可能为负值，修改任意边权，使所有边权非负且任意<u,v>的最短路路径不变。二.题解关键点在于两个：建图。最短路+负边权不难联想到，由于是单源最短路，所以要增加一个超级源点，保证原本的 n 个点都有对应的最短路。边权。最短路松弛...

每日一题 spfa

2020-07-23

0 744

每日一题 [SCOI2007]压缩 (区间dp)

一.题意字符串最长50，求压缩后的最短长度。二.题解考虑维护字符串 s[l....r] 可压缩成的最短长度，第三维维护是否存在 M 。首先是没有 M 的时候 : 有 M 的时候：还要考虑满足条件时可以创造出M: 最后的答案就是三.代码: #include<bits/...

每日一题区间dp

2020-07-21

1 612

2020牛客暑期多校训练营（第二场)

根据难度排序。个人总结向。如果有什么讲的不清楚的欢迎留言私信交流~ D. Duration（签到）题意：给出两个时分秒表示的时间，问相差多少秒。思路：化成秒相减就可以了。代码: #include<bits/stdc++.h> #define pb push_back #defin...

暑假多校

2020-07-19

2 728

2020牛客暑期多校训练营（第一场)

根据难度排序。个人总结向。如果有什么讲的不清楚的欢迎留言私信交流~ F. Infinite String Comparision（字符串+结论）题意：给出两个无限循环串的循环节，比较两个串的大小。思路：假设一个字符串 S 有循环节（不需要是完整循环节） p 和 q ，并且满足，那么也是...

2020-07-19

1 573

每日一题矩阵取数游戏 (区间dp)

一.题意 n*m 的矩阵，每次从每行中取一个数，每行取数的得分 = 被取走的元素值 * 2 ^ i ，i 为第 i 次取数且每次取走的各个元素只能是该元素所在行的行首或行尾，取 m 次，求取数的最大得分和。二.题解因为每次只能取行首或者行尾，所以每行取得顺序都是独立的。由此可以从求最大的得分和...

每日一题区间dp

2020-07-11

7 745

每日一题 Supermarket (优先队列)

一.题意有N件商品，有利润pi和过期时间di，每天只能卖一件商品，过期商品不能再卖，求最大收益是多少。二.题解对于这题，很明显是贪心，肯定是取价格高的物品，但是还要考虑过期时间。本来是可以考虑枚举过期时间，然后在同一过期时间选择价格最高的物品，但其实这样是不对的。例如:450 160 1100...

每日一题优先队列

2020-06-13

1 715

每日一题 [SCOI2005]最大子矩阵 (多维dp)

一.题意 n * m 的矩阵分成 k 组互不重叠的矩阵，求最大的子矩阵和。二.题解特别注意到的是 m 的值为 1 或者 2，所以可以由比较简单的方法写出。考虑代表第一列前 i 个元素和第二列前 j 个元素组成 k 个矩阵的最大值。有以下的递推方程: 由前一状态推出，枚举第一列，枚举第...

每日一题多维dp

2020-06-11

0 699

每日一题失衡天平 (背包dp)

一.题意将一组物品分成两组，每个物品都可以不出现在任何一组。希望两组的重量差异不超过M，求最大化总重量。二.题解首先明显的背包，不过第二维代表的含义稍微做了点修改，代表选取前 i 个物品重量差不超过 j 的最大总重量，那么很明显的有: 不选取第 i 个物品: 选取第 i 个物品并放在天...

每日一题背包dp

2020-06-10

2 896