2023/3/30拼多多笔试

第一题 n, m = map(int, input().split()) dp = [-1] * (m + 1) for j in range(m + 1): dp[j] = -1 dp[0] = 0 for i in range(1, n + 1): s = input() if s == "b": type = int(input()) t = dp[type] dp[type] = max(dp[0], dp[type]) else: type, v = map(int, input().split()) if dp[type] != -1: dp[0] = max(dp[0], dp[type] + v) res = max(dp) print(res)

第一题： #include<bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int a[N],w[N]; char v[N]; int f[N][N]; int main() { int n,m; cin >> n >> m; for(int i = 1 ; i <= n ; i++) { cin >> v[i] >> a[i]; if(v[i] == 'm') { cin >> w[i]; } } for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) { if(v[i] == 'm') f[i][0] = max(f[i - 1][0],f[i - 1][j] + w[i]); else f[i][j] = max(f[i-1][j],f[i - 1][0]); } } int res = 0; for(int i = 0 ; i <= m ; i++) { res = max(f[n][i],res); } cout << res << endl; return 0; }

可惜了 第四题很简单的 不过也很强了

第一题：没看懂题目描述，第二题：dfs，第三题，leetcode原题152，实现思路是选取两个变量同时维护最大值和最小值，因为最小值是负数，可能下一个数碰到就是最大值了，第四题：感觉像求最长非递减序列，通过动态规划可以做（楼主能记住这么多题很棒了！！！）

唯一做出来的第二道题 ``` int findMinCnt(unordered_map<int, vector<pair<int, bool>>>&amp; tree, int root) { //get from root min nums of workers need send to sub tree //返回以当前为根发送最少数量 if (tree.find(root) == tree.end()) { return 0; } auto sub_roots = tree[root]; int ret = 0; for (auto [sub_root, path_ok] : sub_roots) { if (path_ok) { ret += max(findMinCnt(tree, sub_root), 0); } else { ret += max(findMinCnt(tree, sub_root), 1); } } return ret; } ```

爆内存的第一题，写完看到那个ifelse我就不想改成迭代的了

一模一样😅我太菜了

第一题dp了一个小时，没做出来 第二题想了会，觉得应该很难就没想了 第三题想到了dp，但是数字太大，也联想到了给的数字全是2的多少次方，没把两个放在一块想 第四题测试样例都过不了。。。。

请问一下每道题过了一部分也有相应的分数嘛？

第一题就是找最近同类型，然后dp[i] = dp[pre-1] + value。第二题就是个dfs，从子节点回来看子节点是不是修了，修了就把自己和父节点的路修了。第三题就分段，找最远的负数，数值用前缀和记录2的个数。最后一题就是从前往后，写个单调栈，每次出现逆序对就清空栈

还是待笔试是不是就是笔试挂了...

请问pdd笔试全是编程题吗，就四题吗