寒武子星

题解

/ 注册

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

题解 | #[CQOI2007]涂色PAINT#

思路，本题用动态规划来做，dp[l][r]就是以s[l]和s[r]为结尾的字符串最少的颜色涂法。我们要求的字符串厂度为n,所以s[l]和s[r]之间的距离就为n，问题很复杂。我们现在来减小问题规模，如果s[l]等于s[r]也就是说字符串两端的的字符相同，这两端的两个字符记录一次涂改。若不同则在...

Python3

2021-12-09

0 396

题解 | #【模板】完全背包#

以单行dp表示1 - V 容量的背包，dp[j]表示当前循环装满j容量的背包的最大价值。不断通过转移方程在循环中更新列表，最终列表中的最大的值是问题1答案，最后一个值是问题2答案。 while True: try: n, V = map(int, input().split(...

Python3

2021-12-08

0 501

题解 | #【模板】01背包#

主要思路是利用dp找到0-V中每个大小的背包放满可以得到的最大价值。整个背包可放的最大价值就是dp的最大值。dp的最后一个数dp[v]就是放满V大小的背包的最大价值的值。如果没有最大值就输出初始化时候的0，满足输出要求 while True: try: n, V = map(...

Python3

2021-12-08

2 813

题解 | #小红取数#

看了大佬们写的没有看懂，自己写了半天，虽然是用时最多的还是要记录一下，并送给大家参考。问题要点是dp数组如何构建、dp[i][j] 的含义、转移方程如何写。 dp数组如何构建：我以需计算的列表长度n为列，在此基础上添加一列辅助列，代表未取元素时的状态。以对数字K取模后的可能性为行，示例**...

Python3

2021-12-07

6 892

题解 | #字母收集#

while True: try: n, m = map(int, input().split()) l = [] for _ in range(n): l.append(list(input())) dp...

Python3

2021-12-07

0 409

题解 | #【模板】二维差分#

思路：创建一个DP数组，把每次操作修改的起始位置，修正的起始位置记录。利用前缀和把要修改位置填上修改值。最后把DP数组和原始列表相叠加。 while True: try: n, m, q = map(int, input().split()) l = [] ...

Python3

2021-12-07

1 534

题解 | #【模板】二维前缀和#

解题思路大佬们都说了，这里提供下Python实现过程，供大家参考 while True: try: n, m, q = map(int, input().split()) l = [] for _ in range(n): ...

Python3

2021-12-07

1 631

题解 | #abb#

统计每个字符串开始的叠词数量 while True: try: n = int(input()) sn = input() dp = [0 for _ in range(n)] # 用来存放当前i坐标字符串开头的叠词数量 di...

Python3

2021-12-07

2 884

题解 | #不相邻取数#

主要是思路，从第四个数开始，以这个数i为结尾的"不相邻的数的最大和"是其前方i - 3和i- 2的较大值加上当前值 while True: try: n = int(input()) l = list(map(int, input().split())) ...

Python3

2021-12-06

0 570

题解 | #字符个数统计#

一句话搞定 while True: try: print(len(list(set(input())))) except: break

Python3

2021-12-05

0 503