標題:
202404潛力2-切割板材
[打印本頁]
作者:
may
時間:
2024-10-31 16:56
標題:
202404潛力2-切割板材
https://leetcode.cn/problems/selling-pieces-of-wood/description/
[attach]20120[/attach]
切割板材 (Plate)
問題敘述
加工廠最近獲得了一片新的矩形板材,準備將其進行切割後再販售給不同買家。每位買家願意購買任意數量的板材,但該板材必須符合他指定的大小規格。 由於加工廠內設備的限制,切割板材時必須選定一片板材沿著垂直或水平方向一路切到底,不能在中途進行轉彎。舉例來說,如果想在長寬為 3*5 的板材上切出一個長寬為[2, 2]的正方形至少必須經過兩次切割,如下圖所示。
[attach]20118[/attach]
板材在不同方向的紋理是相同的,例如長寬為 4*6 的板材可以旋轉 90 度後作為長寬為 6*4 的板材。加工廠並沒有限制切割板材的次數,且板材經過切割後可以有剩餘沒有被賣出的部分。請寫一支程式幫忙計算一片板材經過切割後後可以獲得的最高營收。
[attach]20119[/attach]
評分說明
此題目測資分成三組,每組測資有多筆測試資料,需答對該組所有測試資料才能獲得該組分數,各組詳細限制如下。 第一組(15分):R = 1、C ≤ 10。 第二組(35分):R = 1。 第三組(50分):無特別限制。
作者:
may
時間:
2024-11-3 17:26
//#include<iostream>
//#include<vector>
//#include<algorithm>
//#include<utility>
#include<bits/stdc++.h>
using namespace std;
int Solve(int R, int C, const vector<vector<int>> &values, vector<vector<int>> &dp)
{
if(dp[R][C]!=-1)return dp[R][C];
int ans = 0;
for(int i=1;i<R;++i)
{
ans = max( Solve(i,C,values,dp)+Solve(R-i,C,values,dp), ans);
}
for(int i=1;i<C;++i)
{
ans = max( Solve(R,i,values,dp)+Solve(R,C-i,values, dp), ans);
}
if(values[R][C]!=0)ans = max(ans,values[R][C]);
dp[R][C] = ans;
return ans;
}
int main()
{
int R, C;
cin >> R >> C;
int N;
cin >> N;
vector<vector<int>> values(201, vector<int>(201, 0));
vector<vector<int>> dp_table(R+1, vector<int>(C+1, -1));
for(int i=0; i<N; ++i)
{
int V, a, b;
cin >> V >> a >> b;
values[a][b] = max(values[a][b], V);
values[b][a] = max(values[b][a], V);
}
cout << Solve(R, C, values, dp_table);
return 0;
}
/*
6 6
1
5 1 1
3 5
4
10 2 2
2 3 1
5 3 4
1 3 1
详解vector二维数组的全部操作(超细图例解析!!!)
*/
複製代碼
作者:
may
時間:
2024-11-3 22:42
//#include <iostream>
//#include <vector>
//#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int main() {
int R, C, N;
cin >> R >> C >> N;
// 建立 DP 陣列並初始化為 0
vector<vector<int>> dp(R + 1, vector<int>(C + 1, 0));
// 讀取每個買家的需求,並更新 DP 陣列
for (int i = 0; i < N; ++i) {
int v, w, h;
cin >> v >> w >> h;
// 如果買家的需求可以放入板材中,則更新 dp[w][h] 和 dp[h][w]
if (w <= R && h <= C) dp[w][h] = max(dp[w][h], v);
if (h <= R && w <= C) dp[h][w] = max(dp[h][w], v);
}
// 動態規劃計算不同大小板材的最大收益
for (int w = 1; w <= R; w++) {
for (int h = 1; h <= C; h++) {
// 橫向切割
for (int i = 1; i < w; i++) {
dp[w][h] = max(dp[w][h], dp[i][h] + dp[w - i][h]);
}
// 縱向切割
for (int j = 1; j < h; j++) {
dp[w][h] = max(dp[w][h], dp[w][j] + dp[w][h - j]);
}
}
}
// 輸出結果,即為 R x C 板材的最大收益
cout << dp[R][C] << endl;
return 0;
}
/*
6 6
1
5 1 1
3 5
4
10 2 2
2 3 1
5 3 4
1 3 1
详解vector二维数组的全部操作(超细图例解析!!!)
*/
複製代碼
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)
Powered by Discuz! 7.2