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