Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Indicații de rezolvare
- Problema se rezolva cu tehnica programării dinamice.
- Putem considera D[i] – puterea maximă a unei soluţii care care începe cu elementul i
- Atunci vom avea recurenţa D[i] = A[i] + max(D[j], unde j aparţine intervalului [si,di])
- Astfel vom obţine o complexitate O(n*n), primind un punctaj de 40 de puncte.
- Pentru 100 de puncte este necesară complexitatea O(nlogn), care se poate obţine folosind arbori de intervale pentru determinarea maximului.
Add Comment
Please, Sign In to add comment
