国庆基地校Day3

今天成绩还算可以

第一梯:就是递归+模拟,难度很低,记住要细心一点,这题处理两个人决策的优先级是重点:比如不能把必杀绝招的处理放在连续攻击后面

第二题:这题用floyd输出的时候要注意统计路上节点,最后的答案需要+2

第三题:这一题用的是最短路径,消除相同字母,我是用直接一路消下来以及两侧分支作比较,然后用最少的消除次数记录这一列,最后把所有列的消除次数比较就行了

第四题:求两串密码的最长上升公共子序列。可以用DP,用 opt1[I,j]表示以 b[j]结尾且是 a[1]-a[i]的子序列的最长公共上升序列的长度,用 opt2[I,j]表示 a[i]=b[j],且以这个数作为结尾的最长上升公共子序列的长度,转移方程如下:


1
2
opt1[I,j]=max{opt1[I-1,j],opt2[I,j]}
opt2[I,j]=max{opt1[I-1,k]+1,1}(k<j,b[k]<b[j],a[i]=b[j])

这种方法的时间复杂度为O(m∧3)

如果想优化可以记录 a[i]=a[l]中的 I,l,在转移时先提前转移 opt2[I,l],这样做就可以减小枚举 k 的范围,因为转移每一个 I,j 都
仅仅从 1 到 m 扫描了一遍。

转移方程如下:
opt1[I,j]=max{opt1[I-1,j],opt2[I,j]}
opt2[I,j]=max{opt2[I,point],opt1[I-1,k]+1,1}
(point=max{l}(a[l]=a[i]),point<k<j,b[k]<b[j],a[i]=b[j])

这题可以反复优化,寻找更好的解题方法

发表评论

电子邮件地址不会被公开。 必填项已用*标注