百度笔试摆火柴，动态规划，个人认为思路正确
然而通过率0%
如果我没记错，好像测试用例是错误的。给20根，怎么可能是5个7一个4呢？5个7一个4是19根。
思路：首先对于火柴用量相同的数，肯定选比较大的那个，小的那个数可以无视了。
所以这里用map来存键值对 key表示用的火柴数量， value为该数量允许摆的最大数字
然后是转移方程
设dp[i]表示用i根火柴能摆出来的最大数，且不能有剩余.
假设7是其中一个可以摆的数，用的火柴为3根，即此时遍历到的键值对为{3，7}
则 i > = 3时，如果dp[i-3] 不为0，说明i-3根火柴能够不剩余的情况下摆出一个最大值，dp[i] = max(dp[i], dp[i-3] * 10 + 7)
每次都要把map重新遍历一遍，这样就能找出最大的
个人觉得自己思路正确，但是不知道错在了哪里
附上debug时的截图
3根的时候最大能摆7，4根摆4，5根摆3，6根摆77（摆两个7）7根摆74（三根的7+4根的4）.以此类推 到了20根，应该是dp[15] * 10 + 3(最后的五根摆3）
20根 我记得例子上是 5个7 一个4 根数是5*3 + 4 = 19，这根本不对啊。。迷惑。我的答案才是对的呀（逃）
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const vector<int> needs{-1, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int max(int a, int b) {
if (a >= b) return a;
return b;
}
int main() {
int n, m;
cin >> n;
cin >> m;
map<int, int> map_;
for (int i = 0; i < m; ++i) {
int temp;
cin >> temp;
int count = needs[temp];
if (map_.find(count) != map_.end())
map_[count] = max(map_[count], temp); //无视同样火柴用量较小的数
else
map_[count] = temp;
}
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; ++i) {
for (auto &item : map_) {
if (i >= item.first) {
if (i == item.first) dp[i] = max(dp[i],item.second);
if (dp[i - item.first] != 0)
dp[i] = max(dp[i], dp[i - item.first] * 10 + item.second);
}
}
}
cout << dp[n];
return 0;
} 
投递美团等公司10个岗位
