牛客网这个bug真有趣

同样一个代码,我在本地跑,在线调试时都会输出正确答案130,但提交就会输出错误答案120。下面是两个图片和代码

#include <iostream>

#include <algorithm>
#include <set>
#include <vector>
#include <unordered_map>

using namespace std;

struct ShopThing{
    int cost;
    int importantValue;
    int masterId;
};
struct MainThing
{
    int cost;
    int importantValue;
    vector<ShopThing> subThings;
};


int main() {
    // 价格 除 10 ,最后在乘 10
    int totalMoney, tmp;
    cin >> totalMoney >> tmp;
    totalMoney = totalMoney / 10;
    unordered_map<int, MainThing> allMainThing;
    for(int i = 0 ; i < tmp; ++i){
        int cost, importantValue, masterId;
        cin >> cost >> importantValue >> masterId;
        if (masterId == 0){
            allMainThing[i + 1].cost = cost / 10;
            allMainThing[i + 1].importantValue = importantValue;
        } else {
            allMainThing[masterId].subThings.push_back({cost / 10, importantValue, masterId});
        }
    }
    // 开始动态规划
    int nowThingId = 0;
    vector<vector<int>> dpList = vector<vector<int>>(allMainThing.size() + 1, vector<int>(totalMoney + 1, 0));
    // dpList[y][x]  y 表示 考虑到1 - y 的所有物品, x表示考虑到现有总钱数为 x*10, 值为最大满意度
    for (auto& nowMainThing : allMainThing){
        ++nowThingId;
        for (int nowMony = 1; nowMony <= totalMoney; ++nowMony ){
            // 考虑 仅主件 主件+1附件 主件+2附件
            // 对每个购买计划,判断是否有足够的钱来买,如果没有就不买,有就买。看看哪个的收益高
            int subAns = 0;
            int cost, importantValue;
            // 仅主件
            cost = nowMainThing.second.cost;
            importantValue = nowMainThing.second.importantValue;
            if (nowMony >= cost){
                subAns = max(dpList[nowThingId - 1][nowMony - cost] + cost * importantValue, subAns);
            } else {
                subAns = max(dpList[nowThingId - 1][nowMony], subAns);
            }
            // 主件 + 附件A 
            if(nowMainThing.second.subThings.size() >= 1){
                cost = nowMainThing.second.cost + nowMainThing.second.subThings[0].cost;
                if (nowMony >= cost){
                    int nowIncome = nowMainThing.second.cost * nowMainThing.second.importantValue;
                    nowIncome +=  nowMainThing.second.subThings[0].cost * nowMainThing.second.subThings[0].importantValue;
                    subAns = max(dpList[nowThingId - 1][nowMony - cost] + nowIncome, subAns);

                }
            } 
            if(nowMainThing.second.subThings.size() == 2){
                cost = nowMainThing.second.cost + nowMainThing.second.subThings[1].cost;
                if (nowMony >= cost){
                    int nowIncome = nowMainThing.second.cost * nowMainThing.second.importantValue;
                    nowIncome +=  nowMainThing.second.subThings[1].cost * nowMainThing.second.subThings[1].importantValue;
                    subAns = max(dpList[nowThingId - 1][nowMony - cost] + nowIncome, subAns);
                }
                
                cost = nowMainThing.second.cost + \
                nowMainThing.second.subThings[0].cost + \
                nowMainThing.second.subThings[1].cost;
                if (nowMony >= cost){
                    int nowIncome = nowMainThing.second.cost * nowMainThing.second.importantValue;
                    nowIncome +=  nowMainThing.second.subThings[0].cost * nowMainThing.second.subThings[0].importantValue;
                    nowIncome +=  nowMainThing.second.subThings[1].cost * nowMainThing.second.subThings[1].importantValue;
                    subAns = max(dpList[nowThingId - 1][nowMony - cost] + nowIncome, subAns);

                }

            } 
            dpList[nowThingId][nowMony] = subAns;
        }   
    }
    cout << dpList[allMainThing.size()][totalMoney] * 10 <<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

全部评论

相关推荐

ResourceUtilization:算法很难了,现在都需要相关论文还有对应的实习,可以先试试中厂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务