[SCOI2007]压缩题目题解

zzugzx

发表于 2020-07-14 11:11:26

题目链接题意：题解：最后答案取dp[1][n][0/1]的最小值即可 AC代码 /* Author : zzugzx Lang : C++ Blog : blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h 展开全文

19_hanhan

发表于 2020-07-16 00:00:49

好久没写每日一题了，今天开始重拾算法QAQ 题目题目描述：给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有展开全文

hnust_yangyanjun

发表于 2020-07-21 00:49:13

题意：给与一个长度不超过50的字符串，它可以按下列方式压缩：M是开始，R是重复从前一个M开始的字符串。求字符串压缩后的最短长度。思路：区间dp:dp[i][j][0/1]:dp[i][j][0]表示从i到j这段字符串中没有有M、dp[i][j][1]表示从i到j这段字符串中可以出现M的最少字符数。展开全文

江三

发表于 2020-07-21 09:44:34

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

sunrise__sunrise

发表于 2020-07-15 16:48:52

题目描述给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。bcdcdcdcd可以压缩为b 展开全文

sunsetcolors

发表于 2020-07-14 13:01:16

[SCOI2007]压缩题目地址： https://ac.nowcoder.com/acm/problem/20252 基本思路：题目没有给数据范围QAQ，去查了一下原题，所以考虑区间;我们如果朴素的去区间，设表示范围能被压缩的最小长度，那么我们容易得到如下的转移方程: 不压缩，正常的长展开全文

Eihuvita.

发表于 2020-07-18 21:54:10

题目描述给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为展开全文

⊙__⊙

发表于 2020-07-14 23:17:40

题意:给出一个小写字符串，让你按照题目规则压缩成最短的字符串。压缩规则: 重复的部分可以压缩在一起，M表示重复部分开始标记，R表示从M开始的部分重复一次。分析: 如果没有M的条件，我们考虑区间dp[i][j][0]表示区间[i:j]没有M，那么我们就直接压缩dp[i][j][0]=min(dp[ 展开全文

num73

发表于 2020-07-15 09:38:06

[SCOI2007]压缩题解很显然是一个dp。。。很妙的一个dp,很难的一个dp。。。因为M，R存在造成的不同结果，需要分类讨论。记: dp[i][j][0]为区间[i,j]不加M时最短长度 dp[i][j][1]为区间[i,j]有M时最短长度那么转移方程为：dp[i][j][0]=min( 展开全文

Severus.

发表于 2020-07-14 12:56:08

题目描述给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。bcdcdcdcd可以压缩为b 展开全文

相关比赛

等你来战