1361 問(wèn)題 A: 矩形分割
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 175 解決: 63
題目描述
出于某些方面的需求，我們要把一塊N×M的木板切成一個(gè)個(gè)1×1的小方塊。
對(duì)于一塊木板，我們只能從某條橫線或者某條豎線（要在方格線上），而且這木板是不均勻的，從不同的線切割下去要花不同的代價(jià)。而且，對(duì)于一塊木板，切割一次以后就被分割成兩塊，而且不能把這兩塊木板拼在一起然后一刀切成四塊，只能兩塊分別再進(jìn)行一次切割。
現(xiàn)在，給出從不同的線切割所要花的代價(jià)，求把整塊木板分割成1×1塊小方塊所需要耗費(fèi)的最小代價(jià)。
輸入
輸入文件第一行包括N和M，表示長(zhǎng)N寬M的矩陣。
第二行包括N-1個(gè)非負(fù)整數(shù)，分別表示沿著N-1條橫線切割的代價(jià)。
第二行包括M-1個(gè)非負(fù)整數(shù)，分別表示沿著M-1條豎線切割的代價(jià)。
輸出
輸出一個(gè)整數(shù)，表示最小代價(jià)。
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情