diff options
-rw-r--r-- | max_total_damage_spell_casting.c | 42 | ||||
-rw-r--r-- | max_total_damage_spell_casting.py | 45 |
2 files changed, 87 insertions, 0 deletions
diff --git a/max_total_damage_spell_casting.c b/max_total_damage_spell_casting.c new file mode 100644 index 0000000..d229f6f --- /dev/null +++ b/max_total_damage_spell_casting.c @@ -0,0 +1,42 @@ +// 3186. Maximum Total Damage With Spell Casting +#include "leetcode.h" + +/* + * a magician has various spells. you are given an array 'power', where each + * element represents the damage of a spell. multiple spells can have the same + * damage value. it is a known fact that if a magician decides to cast a spell + * with a damage of 'power[i]', they cannot cast any spell with a damage of + * 'power[i] - 2', 'power[i] - 1', 'power[i] + 1', or 'power[i] + 2'. each spell + * can only be cast once. return the maximum possible total damage that a + * magician can cast. + */ + +long long maximumTotalDamage(int *power, int powerSize) { + long long freq[100001] = {0}, dp[100001] = {0}; + for (int i = 0; i < powerSize; i++) + freq[power[i]]++; + int keys[100001], n = 0; + for (int i = 0; i <= 100000; i++) + if (freq[i]) + keys[n++] = i; + dp[0] = freq[keys[0]] * keys[0]; + for (int i = 1; i < n; i++) { + long long take = freq[keys[i]] * keys[i]; + int prev = -1; + for (int j = i - 1; j >= 0; j--) + if (keys[j] <= keys[i] - 3) { + prev = j; + break; + } + if (prev >= 0) + take += dp[prev]; + dp[i] = dp[i - 1] > take ? dp[i - 1] : take; + } + return dp[n - 1]; +} + +int main() { + int p1[] = {1, 1, 3, 4}, p2[] = {7, 1, 6, 6}; + printf("%lld\n", maximumTotalDamage(p1, ARRAY_SIZE(p1))); // expect: 6 + printf("%lld\n", maximumTotalDamage(p2, ARRAY_SIZE(p2))); // expect: 13 +} diff --git a/max_total_damage_spell_casting.py b/max_total_damage_spell_casting.py new file mode 100644 index 0000000..946bf15 --- /dev/null +++ b/max_total_damage_spell_casting.py @@ -0,0 +1,45 @@ +# 3186. Maximum Total Damage With Spell Casting +from collections import Counter + +""" +a magician has various spells. you are given an array 'power', where each +element represents the damage of a spell. multiple spells can have the same +damage value. it is a known fact that if a magician decides to cast a spell +with a damage of 'power[i]', they cannot cast any spell with a damage of +'power[i] - 2', 'power[i] - 1', 'power[i] + 1', or 'power[i] + 2'. each spell +can only be cast once. return the maximum possible total damage that a +magician can cast. +""" + + +class Solution(object): + def maximumTotalDamage(self, power): + """ + :type power: List[int] + :rtype: int + """ + freq = Counter(power) + keys = sorted(freq) + n = len(keys) + dp = [0] * n + dp[0] = freq[keys[0]] * keys[0] + for i in range(1, n): + take = freq[keys[i]] * keys[i] + l, r, ans = 0, i - 1, -1 + while l <= r: + mid = (l + r) // 2 + if keys[mid] <= keys[i] - 3: + ans = mid + l = mid + 1 + else: + r = mid - 1 + if ans >= 0: + take += dp[ans] + dp[i] = max(dp[i - 1], take) + return dp[-1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumTotalDamage(power=[1, 1, 3, 4])) + print(obj.maximumTotalDamage(power=[7, 1, 6, 6])) |