百度3月7笔试题求解

我AC了，就整个长度n的列表，每位记录以当前位为end的白魔法和黑魔法数。假设list[n] = [white,black]，那我们读到n+1位的时候，如果是正数，那黑魔法的方案数会多list[n][1]种，白魔法的方案数会多list[n][0]+1种（因为会多只有第n+1本身的这种情况），是负数的话反过来，遍历一次以后把列表每个元素的[0]和[1]相加输出就ok啦，dp问题

我用的回溯，只有82%

可以看下我的题解

超时不会提醒吗

借楼问有没有做A卷的佬，其他踢没A但至少有思路，第一题子序列拆分一点思路都没😥

n = int(input()) num = list(map(int, input().split())) l = len(num) count = [0, 0] # 存储白，黑的个数 if num[0] > 0: count[0] = 1 else: count[1] = 1 res_0, res_1 = count[0], count[1] for i in range(1, l): if num[i] > 0: count[0], count[1] = count[0] + 1, count[1] else: count[0], count[1] = count[1], count[0] +1 res_0 += count[0] res_1 += count[1] print(res_1, res_0) ac了，可以看作指针滑动，以当前指针所指元素为尾考虑的话，很类似双指针滑动那道题。 就出现了状态转移公式，对应在代码里，自己看吧

有的用例超时了吧

第一超时，第二t=m［i］

（不同指的就是不同段连续释放组成的结果） 这句话应该代表最后释放的魔法序列不同 比如 [-1, 1, -1] 可以分成 一、[-1] [1, -1] 魔法序列就是（黑， 黑） 二、[-1, 1] [-1] 魔法序列也是（黑，黑） 这两种算作一种方案数

你这肯定超时啊，动态规划不就行了

欸我去你们一说超时那还真是，问题是他也不提醒我也没想到是超时了

蹲，用的dp复杂度On, 也只过27

怀疑是不是python语言有问题啊On了只过27%

动态规划。 l = [1,-1,1,-1,1] 一维转移方程：dp[i] = l[i]*dp[i-1], dp[i]表示用i个连续时的乘积；两次循环，小循环从后面开始，每大循环计算一次当前dp中正负数，最后求和； 二维转移方差：dp[i][j] = l[i]*dp[i-1][j-1]，dp[i][j]表示每次l中第i位置的数和其余与之连续的j-1个数的乘积，最后直接计算二维矩阵的正负个数； 27%可能是超时，82%应该是没用1，-1代替，导致数据超了

m[i] 的范围在-10^9到10^9之间，如果你每次都乘m[i]那你的t值会非常巨大

这样一直乘是不是会爆了。。

黑魔法是DP，难度都不高

楼主，这是春招吗

请问笔试一共是三道编程题吗？

百度的笔试是在牛客网上的吗？可以用本地ide吗