Մատրիցների բազմապատկում
Տրված են
n մատրիցներ , որոնց չափերն են համապատասխանաբար։ Մատրիցները դասավորված են ձախից աջ, 1-ից մինչև n: Թույլատրելի է փակագծեր տեղադրել՝ որոշ բազմապատկումներ նախապատվությամբ կատարելու համար։Ո՞րն է բոլոր մատրիցները բազմապատկելու համար անհրաժեշտ գործողությունների նվազագույն քանակը:
💡
Երբ չափի մատրիցը բազմապատկվում է մատրիցով, կատարվում է թվով գործողություն։
Մուտք
Մուտքի առաջին տողում տրված է
n ամբողջ թիվը ()։Հաջորդ
n տողերում տրված են յուրաքանչյուր մատրիցի և չափերը (1 ≤ ≤ 1000)։Ենթադրվում է, որ բոլոր
i ∈ {1, 2, ..., n-1}-երի համար։Ելք
Հարկավոր է տպել բոլոր մատրիցները բազմապատկելու համար պահանջվող նվազագույն գործողությունների քանակը:
Օրինակներ
Մուտք | Ելք |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB