diff options
author | Jack Sangdahl <[email protected]> | 2025-10-10 21:45:49 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-10-10 21:45:49 -0600 |
commit | a5f938a020f2ddb10668e8d10a146027ea1807cd (patch) | |
tree | 29bb7777b7855919a9be47b3fd9b3f30d1f007ea /max_total_damage_spell_casting.c | |
parent | 24e6d065fa365234f842125c268e75aa17c31388 (diff) | |
download | leetcode-a5f938a020f2ddb10668e8d10a146027ea1807cd.tar.gz leetcode-a5f938a020f2ddb10668e8d10a146027ea1807cd.zip |
Diffstat (limited to 'max_total_damage_spell_casting.c')
-rw-r--r-- | max_total_damage_spell_casting.c | 42 |
1 files changed, 42 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 +} |