江三

题解

/ 注册

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

每日一题 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

每日一题矩阵取数游戏 (区间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 897

每日一题德玛西亚万岁 (状压dp)

一.题意德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土地标记为0表示为高山峻岭或...

每日一题状压dp

2020-06-09

0 600

每日一题小A与小B 双向BFS

一.题意这道题要求小A和小B最早的相遇时间。而小A的行走规则是：每次可以走8个方向，每次走一步。小B的行走规则是：每次可以走4个方向，但每次走两步（两步不一定是要同方向）。二.题解很明显分别对两个人进行bfs 计算出到达每个点两个人到达的最短时间然后枚举两个人都能达到的点，比较取较大值，再与a...

每日一题 bfs

2020-06-09

0 579