ant mock
这道题01背包只a了一半,超内存了:
参考:作者:Venn299
链接:https://www.nowcoder.com/exam/test/82624987/submission?examPageSource=Company&pid=55292243&testCallback=https%3A%2F%2Fwww.nowcoder.com%2Fexam%2Fcompany%3FcurrentTab%3Drecommand%26jobId%3D100%26keyword%3D%E8%9A%82%E8%9A%81%26selectStatus%3D0&testclass=%E8%BD%AF%E4%BB%B6%E5%BC%80%E5%8F%91
int main() { long long ans = -1; long long temp = 0; int curp = x; function <void(int)> dfs = [&](int idx){ if(idx == n){ ans = max(ans,temp); return; } for(int j=0;j<pricevec[idx].size();j++){ if(curp-pricevec[idx][j] < 0) continue; curp -= pricevec[idx][j]; temp += valuevec[idx][j]; dfs(idx+1); curp += pricevec[idx][j]; temp -= valuevec[idx][j]; } }; dfs(0); printf("%lld",ans); }
目前想的是dp,看到有dijkstra做的,明天再想