मैट्रिक्स गुणन
दिए गए
n मैट्रिक्स , जिनके आयाम हैं। ये मैट्रिक्स बाएँ से दाएँ क्रम में 1 से n तक व्यवस्थित हैं। आपको कोष्ठक लगाने की अनुमति है, ताकि कुछ गुणनों को प्राथमिकता दी जा सके।प्रश्न: सभी मैट्रिक्स को गुणा करने में लगने वाले कुल ऑपरेशन्स की न्यूनतम संख्या कितनी होगी?
💡
जब हम एक मैट्रिक्स को मैट्रिक्स से गुणा करते हैं, तो ऑपरेशन्स किए जाते हैं।
Input
पहली पंक्ति में एक एकल पूर्णांक
n () दिया होता है।अगली
n पंक्तियों में प्रत्येक मैट्रिक्स के आयाम दिए होते हैं (1 ≤ ≤ 1000)।यह सुनिश्चित किया जाता है कि हो, जहाँ ।
Output
कार्यक्रम को उन ऑपरेशन्स की न्यूनतम संख्या प्रिंट करनी चाहिए, जो सभी मैट्रिक्स के गुणन के लिए आवश्यक हैं।
उदाहरण
इनपुट | आउटपुट |
3
2 3
3 4
4 6 | 72 |
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB