国庆嗨皮day3

第1题递归+模拟,难度超低只不过要细心一点哈注意处理两个人决策的优先级:比如不

能把必杀绝招的处理放在连续攻击后面

第2题直接 floyd输出的时候统计路上节点即可就是注意一点 .. 答案要+2

第3题将地图中相邻且相同的点距离为 0,不相同为 1,然后建立两个假点,源点 s 和最

上面一排所有点相连,距离为 0;同样的,汇点 t和最下面一排所有点相连,距离也为

0;接下来就是求 s 到 t 的最短路 ans,输出 ans+1 即为答案。

第4题

就是求两个序列的最长上升公共子序列,而对于求最长公

共子序列和最长上升序列这两个动态规划的基础模型,我们已经十分熟悉。因

此本题可以考虑在经典问题的经典解法的基础上进行改动,于是我们想到,可

以先求两个序列的最长公共序列,再对其求最长上升序列,即为答案。

转移方程如下:

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])

发表评论

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