首页 > [HAOI2016]字符合并
开通博客写题解
头像 shyyhs
发表于 2021-03-11 19:26:40
思路 可能是个套路题,但是没见过...第一眼觉得是个区间,但是中间的状态总是弄不清楚...然后看了题解是状压+区间.令表示为区间合并成字符串所获得的最大代价.区间的划分有个优化就是,每次只能是这种才能形成,然后就行划分,当区间是这个长度的时候进行一次答案统计即可. 代码 #include <b 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 jzdx（hjh）
发表于 2021-03-16 15:55:43
题号 NC19997名称 [HAOI2016]字符合并来源 [HAOI2016] 题目描述 有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。 样例 输入 3 2 101 1 10 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2021-03-12 00:02:58
做法：状压dp+区间dp 样例解释 第 3 行到第 6 行表示长度为 2 的 4 种 01 串合并方案。00→1，得 10 分，01→1 得 10 分，10→0 得 20 分，11→1 得 30 分。 思路 设是在区间中状态为的最大分数 因为m个字符能合并成1个字符 所以我们可以求出在len 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Eihuvita.
发表于 2021-03-13 15:47:40
题意 给出一个长度为的01串 然后将相邻的个字符合并 得到一个新的字符并且获得一定的分数 解释一下样例 101 合并后面的01 得到一个1 然后分数是10 然后就变成11了 再合并11 就得到一个 1分数是30 所以总的分数就是40 设为在范围状态为s的最大的值 在之间我们都以m为长度将每一个都合并 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2020-07-17 12:04:16
[HAOI2016]字符合并 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-03-11 20:04:58
题目描述 给你长度为的一个字符串，你可以选择长度为的一段合并成一个字符，并且会得到一个价值。现在通过二进制中大小在后面的行中依次给出，问你这个字符串在最优的合并情况下，可以得到的最大价值是多少。 Solution 通过题目发现，所以最终得到的字符串一定是一个的字符串，如果存在大于情况，一定可以再合并 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”