Re: [閒聊] 每日leetcode已回收
題目翻譯：
有一堆書 給你他們的寬跟高
跟一個寬shelfWidth的書架
每次放書都要照順序垂直放進去
不可以疊在一起
放滿了就放個隔板 然後去下一層放
請問最少要多少高度的書架才能裝下所有書
思路：
我原本沒看到要找順序
所以就sort然後從大賽到小
幹咧
```cpp
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth)
{
int n = books.size();
sort(books.begin() , books.end() , [](vector<int> &a , vector<int> &b){
return a[1]>b[1];
} );
for(int i = 0 ; i < n ; i ++)cout<<books[i][0]<<" "<<books[i][1]<<" ";
vector<int> used(n,0);
int now = 0;
int h = 0;
int nowh = 0;
int noww = 0;
while(now < n)
{
noww = 0;
nowh = -1;
for(int i = 0 ; i < n ; i ++)
{
if(used[i])continue;
if(noww + books[i][0] > shelfWidth)continue;
if(nowh == -1)nowh = books[i][1];
noww += books[i][0];
now ++;
used[i] = 1;
}
h += nowh;
}
return h;
}
};
```
思路2：
看了提示 dp
把每個書都當作是最後一本書
往前找最後一層的書跟他們原本的高度
這樣就可以用dp來找所有的高度了
套路題= =
好像還有recursive 的做法
累累
```cpp
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth)
{
int n = books.size();
vector<int> paper(n+1,99999999);
paper[0]=0;
for(int i = 1 ; i <= n ; i ++)
{
int cw = books[i-1][0];
int allw = cw;
int ch = books[i-1][1];
paper[i] = paper[i-1]+ch;
for(int j = i -1 ; j > 0 ; j --)
{
if(allw + books[j-1][0] > shelfWidth)break;
allw += books[j-1][0];
ch = max(ch , books[j-1][1]);
paper[i] = min(paper[i] , paper[j-1] + ch);
}
}
return paper[n];
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.32.222 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722404476.A.555.html
推
07/31 13:42,
1年前
, 1F
07/31 13:42, 1F
推
07/31 13:46,
1年前
, 2F
07/31 13:46, 2F
推
07/31 13:49,
1年前
, 3F
07/31 13:49, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 601 之 1552 篇)：