Հանքերի պաշտպանությունը
Վիդեոխաղեր խաղալիս ռեսուրսների ճիշտ կառավարումը անչափ կարևոր է:
Տրված են
n ոսկու հանքեր, որոնք գտնվում են տարբեր կոորդինատներում : Յուրաքանչյուր հանք կարող է արտադրել որոշակի քանակի ոսկի : Սակայն, այդ հանքերը պաշտպանելը թշնամիներից բավականին պահանջկոտ է և մեծ քանակի էներգիա է պահանջում։ Բարեբախտաբար, յուրաքանչյուր հանքից կարելի է նաև ստանալ որոշակի քանակի էներգիա :Ձեր նպատակը միառանձին (շարունակական) հատված ընտրելն է այդ հանքերից և պաշտպանել դրանք՝ հնարավորինս մեծ ոսկի ստանալու համար։ Եթե ընտրում եք որևէ հատված, ապա անհրաժեշտ է, որ այն պաշտպանելու համար ունենաք էներգիա, որը նվազագույնը հավասար լինի այդ հատվածի երկարությանը։
Որքա՞ն ոսկի կարելի է ձեռք բերել անվտանգ կերպով:
Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը (1 ≤ n ≤ )։Հաջորդ
n տողերից յուրաքանչյուրում տրված են 3 ամբողջ թվեր , , (1 ≤ ≤ ), որոնք համապատասխանաբար ցույց են տալիս հանքի կոորդինատը, որքան ոսկի է արտադրում, և ինչքան էներգիա է տալիս։ Բոլոր կոորդինատները տարբեր են և ներկայացված են աճող հաջորդականություն:Ելք
Ծրագիրը պետք է տպի այն առավելագույն ոսկու քանակը, որը հնարավոր է ապահով կերպով ստանալ հանքերից:
Օրինակներ
Մուտք | Ելք |
4
1 5 1
2 7 2
5 4 1
8 15 1 | 16 |
2
1 4 1
4 5 1 | 5 |
Բացատրություն
- Առաջին օրինակում → 16
X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Energy | 1 | 2 | ㅤ | ㅤ | 1 | ㅤ | ㅤ | 1 |
Gold | 5 | 7 | ㅤ | ㅤ | 4 | ㅤ | ㅤ | 15 |
Կարելի է ընտրել առաջին 3 հանքերը ⇒ հատվածի երկարությունը կլինի
5-1 = 4 (կոորդինատների ծայրակետերը ներառելով), իսկ հանքերից ստացվող ընդհանուր էներգիան 1+2+1 = 4 է։ Ստացվող ոսկին 5+7+4 = 16 է։- Երկրորդ օրինակում → 5
X | 1 | 2 | 3 | 4 |
Energy | 1 | ㅤ | ㅤ | 1 |
Gold | 4 | ㅤ | ㅤ | 5 |
Կարելի է ընտրել վերջին ոսկու հանքը ⇒ հատվածի երկարությունը
0 է, համապատասխան էներգիան 1 է, իսկ ոսկու քանակը 5:Հուշում 1
Երբ կիրառում եք «Բաժանիր և տիրիր» մոտեցում, գուցե անհրաժեշտ լինի տարբեր եղանակներ օգտագործել ձախ և աջ հատվածների համար:
Հուշում 2
Փորձեք հաշվել այն պատասխանները, որոնք անցնում են միջնակետով:
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB