牛客网这个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")