首页| 新闻| 娱乐| 游戏| 科普| 文学| 编程| 系统| 数据库| 建站| 学院| 产品| 网管| 维修| 办公| 热点
题意: 话的长度为n,语句里的字符不是2就是3。 呃喵的智力非常有限,只有m点。她每次操作可以交换两个相邻的字符,然而代价是智力-2。 现在问你,在使得自己智力不降为负数的条件下,呃喵最多能使这个字符串中有多少个子串”233”呢? 如”2333”中有一个”233”,”232323”中没有”233” 1 <= n <= 100, 0 <= m <= 100
题解: 一看到正解是O(n4)的而我是O(n3)的吓得我赶紧写一篇题解 首先要发现两个性质 1、所有的操作方式都能只用前移完成 2、交换后同种字符间的相对顺序不会改变 考虑dp,根据性质1转移时可以只用位置i前移得到所有状态 最暴力的状态是f[i][s][k],表示处理了前i个位置,串长的样子是s,得到k个233最少交换几次。 根据性质2,假设s[i+1]为2,那他最终移动到的位置不会比上一个2要前,所以我们不需要记录整个串长什么样子,只需要记录上一个2出现的位置即可。3也是同理。 那么状态就变成了f[i][j1][j2][k],j1和j2分别表示2和3上一次出现位置。再观察发现j1和j2必定有一个是i,所以可以省掉一维。 最终状态就是f[i][j][k][o1][o2]。表示考虑了前i位,上一个与第i位不同的字符在位置j,匹配出k个233,第i位为o1,第j位为o2最少交换几次。o1,o2的取值为0,1,2。0表示这是一个2。1表示这是一个3,并且在他后面加一个3可以贡献答案。2就表示不能贡献答案的3。 考虑转移,枚举新加入的位转移到哪个位置很容易,但是O(n4)不稳啊。。 观察一下,发现枚举位置转移一个非常辣鸡的地方在于,他做了很多重复的转移,比如: 枚举i+1这个2要转移到中间那一段时,转移的状态其实都是f[i+1][j1][k+1][2][0]。而且考虑一下把这个2换到前面,破坏一个答案肯定不是最优的。所以特殊的转移只有换一次换到位置i。而中间一段同样的转移,用个数组记录,最后扫一遍就好了。 分析一下3的转移,也有类似的浪费,同样的方法处理即可。 于是复杂度就将到O(n3)辣~~ 就是写起来有点恶心
索泰发布一款GTX 1070 Mini迷
AMD新旗舰显卡轻松干翻NVIDIA
索泰发布一款GTX 1070 Mini迷你版本:小机
芭蕾舞蹈表演,真实美到极致
下午茶时间,悠然自得的休憩
充斥这繁华奢靡气息的城市迪拜风景图片
从山间到田野再到大海美丽的自然风景图片
肉食主义者的最爱美食烤肉图片
夏日甜心草莓美食图片
人逢知己千杯少,喝酒搞笑图集
搞笑试卷,学生恶搞答题
新闻热点
疑难解答
图片精选
Dictionary数据类型在Darwin视频服
可穿戴手势识别控制器
网友关注