江三

题解

/ 注册

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

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