🐜笔试第三题TLE

人晕了,第一次用邻接矩阵oom23%,改了空间复杂度之后TLE58%,这题还有啥不超时的方法啊,转正还寄了。。鼠鼠我啊真要失业了捏
全部评论
几号答辩的??
点赞 回复 分享
发布于 08-28 23:24 广东

相关推荐

09-19 17:51
东南大学 C++
第一题用0-1背包的思想,但是一直只能过64% ,好想知道为什么#include<iostream>#include<algorithm>#include <vector>using namespace std;bool isValid (vector<int>& weight, int bagSize, int q) {    int len = weight.size();    vector<vector<bool>> dp(len + 1, vector<bool>(bagSize + 1, false));    dp[0][0] = true;    bool flag = false;    for (int i = 1; i < len; ++i) {        for (int j = 0; j <= bagSize; ++j) {            if (j < weight[i-1]) dp[i][j] = dp[i-1][j];            else if (j == weight[i-1]) dp[i][j] = true;            else if (weight[i-1] < j && weight[i-1]  + q >= j) dp[i][j] = true;            else dp[i][j] = dp[i-1][j - weight[i-1]];            if (j == bagSize && dp[i][j]) return true;        }    }    return dp[len][bagSize];}int main(void) {    int t;    cin >> t;    while (t--) {        int bagSize, n, q;        cin >> bagSize >> n >> q;        vector<int> weight(n);        for (int i = 0; i < n; ++i) cin >> weight[i];        if (isValid(weight, bagSize, q)) cout << "YES" << endl;        else cout << "NO" << endl;    }}
投递小米集团等公司10个岗位
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务