拼多多3/30思路

1-闯关
dp[i]=max(dp[i],dp[j-1]+val[i]); //满足条件 ch[j]=='b'&& kind[j] == kind[i]
① 可以暴力枚举i,j，当然这样写是O(n*n)，需要优化
②  定义一个vector<int> vec[kind]存下标pos，其中下标满足ch[pos]=='b'&&kind[pos]==kind，这样能卡过(1700ms通过)就没继续优化了。
③ 继续优化可以发现对于一个kind，不需要遍历②的所有pos，而只需找到最大的dp[pos-1]即可，那么就可以继续优化到O(n)
--------------
2-最少施工队
树形dp，转移方程
dp[fa]+=(dp[son]==0? cost[{fa,son}]:dp[son])
① dp[i]表示以i的子树所需的施工队,cost[{fa,son}]表示fa-son这条边是0还是1
② 解释下方程，如果son子树已经需要派施工队去，那么fa-son这条边就不需要多的施工队了，否则看该边是0还是1
--------------
3-连续子数组最大乘积
①可以发现0会把数组划分成一段一段，答案区间一定不会包含0
②假如全部是正数，那么区间的乘积可以用2的幂次表示，所以记录2的幂次和即可(mp[8]=3，mp[4]=2)
②对于一段不含0的区间，需要让负号为偶数，所有如果区间是奇数个负数，那么就删去左边第一个负数 或者 右边第一个负数。
我的做法是用map<pair<int,int>,int> >mp存下所有的合法区间,mp[{l,r}]=sum，然后遍历mp求值。
tips：输出-1的数据只有6%，通过94%或者96%可能是因为下面的数据
--------------
5         |    5    
1 1 1 1 1   |   1 -1 1 1 1
4-最少操作
①从后往前构造，如果a[n]这个数被置为0会怎么样。
②a[n]不用置为0是数组什么情况
实际上只有 2 3  1 4 4 4 5 5这样的才会说少用次数，不需要去消除4和5，而 2 4 3 1 4 4  5就不能保留4 。
倒着去求就可以
--------------
代码是再牛客上直接写的，本地没有保存