blob: 1201823c85ad0fd0a7c3eed6c5b4a57e6c2ddfa7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include "leetcode.h"
class Solution {
public:
int tallestBillboard(vector<int> &rods) {
unordered_map<int, int> dp;
dp[0] = 0;
for (int i : rods) {
unordered_map<int, int> tmp;
for (auto &it : dp) {
int diff = it.first;
tmp[diff + i] = max(tmp[diff + i], dp[diff] + i);
tmp[diff - i] = max(tmp[diff - i], dp[diff]);
}
dp.clear();
dp.insert(tmp.begin(), tmp.end());
}
return dp[0];
}
};
int main() {
Solution obj;
vector<int> rods = {1, 2, 3, 6};
cout << obj.tallestBillboard(rods);
}
|