cf div3 4/22 2020 赛后敢想

也没什么好总结的。
太久没打cf,c题看错题目,d题没初始化debug了半天,a题感觉比b难,两题的实现都超过了我的预期

c题,题意是:给出一个有正有负的序列, 你要从中找出长度最长的正负交替的子序列,使得这个子序列Σ最大
然后看错题,果断白给20分钟。把长度最长这个条件给去掉了。

如果没有这个条件,怎么做呢?我的想法是dp,但是不知道成功与否。

能不能dp来维护,我想的是维护最后一个正数。 因为我们直观来取的话,肯定是取正值的。那么对于每一个正值,都有两种情况: 选它前面的负数,或者取消上一个正数的选择将其代替

您可能还喜欢...

发表评论

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