牛客网这个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")
查看18道真题和解析