首页 > Subsequences (hard version)
开通博客写题解
头像 sunrise__sunrise
发表于 2021-02-03 22:52:28
中文题意 给你长度为n的字符串S，要你构造出大小为m的子序列集合。并且子序列的价值等于原序列长度减掉子序列长度，现在问你构造出最小的子序列集合的总价值是多少，如果无法构造输出负一。 Solution 动态规划解题，我们要构造出大小为m的子序列集合，那么我们根据子序列的特性，前面字符只能保留或者删除 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2021-02-04 11:39:12
传送门 如果想到了的话,这题就不难了。 首先解决一个简单的问题,如何求出串有多少不同的子序列 定义为以的长度为的子序列个数 ,意思是选或者不选都是一种选择 但是有重复,考虑且时 形成的子序列后面接上或者接上是等价的 所以真正的转移方程是 也就是找到最近的一个满足条件的,然后去掉的方案数 那么这题就简 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 shyyhs
发表于 2021-02-03 02:20:23
思路: 我们令表示到了第i个位子,长度为j且不同的字符串有多少.很显然,到了第i个位子,长度为j,第j个位子可以选,然后前面选取j-1个长度,或者第j个位子不选,前面选取j的长度.但是这样会有重复的,这时就要容斥一下了,所包含的重复状态一定是.然后第i个选长度为0的方案数都是1.这个题就解决了.当然 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 MYCui_
发表于 2021-02-03 14:19:33
CF1183H Subsequences (hard version) 题意： 给定一个长度为 () 的字符串 以及 一个数字 ()，规定串的每个子序列的价值为 ，现在要求你求出 个本质不同的子序列使得价值最小。 ps.本质不同 指的是：子序列的内容不同，而不是单纯的子序列的位置不同。 具体 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 (́安◞౪◟排‵)
发表于 2021-02-03 16:49:45
比较妙的DP题设计dp[i][j]表示前i个字符中选j个字符可以构成的方案pre[i]代表ascall为i的字符上一次出现的位置转移方程有容斥的思想,如下dp[i][j]=j==0?dp[i-1][j]:dp[i-1][j]+dp[i-1][j-1]-dp[(pre[a[i]]-1)==-1?n:( 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 熠丶
发表于 2021-02-08 10:42:37
做法：动态规划 思路 用pre[i]存上一次'a'+i这个字母出现的位置，设dp[i][j]:前i个字符中长度为j的数量 如果一个字母上次出现过，需要减去dp[pre[s[i]-'a']-1][j-1]重复的子序列 每次删最少的字符即长度越长的子序列优先 代码 // Problem: Subse 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hunxuewangzi
发表于 2021-02-18 10:44:40
题目链接 题目大意 给你一个长度为的字符串 要你找出个不同的子序列，使得k个不同的子序列总价值最小是多少 一个子序列的价值为删去的字符长度 空串也为子序列 题目思路 其实不难就是要明白怎么设dp方程 设 为前i个字符构造长度为j的不同子序列长度 显然 就是选和不选第i个字符的问题 但是会有重复 假设 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2021-02-20 12:42:05
题意： 长度为n的字符串S，现在要找出k个不同的子序列，使得这些序列的总价值最低一个序列的价值等于删去的字符长度（空串也算子序列）1≤n≤100,1≤k≤10^12^ 题解： 一看就是dp，我们先想想串a可以有多少不同的子序列dp[i][j]表示前i个字符构造出来的长度为j的子序列数量转移方程不难得 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”