Board logo

標題: 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

  1. //#include<iostream>
  2. //#include<vector>
  3. //#include<algorithm>
  4. //#include<utility>
  5. #include<bits/stdc++.h>
  6. using namespace std;

  7. int Solve(int R, int C, const vector<vector<int>> &values, vector<vector<int>> &dp)
  8. {
  9.     if(dp[R][C]!=-1)return dp[R][C];
  10.     int ans = 0;
  11.     for(int i=1;i<R;++i)
  12.     {
  13.         ans = max( Solve(i,C,values,dp)+Solve(R-i,C,values,dp), ans);
  14.     }
  15.     for(int i=1;i<C;++i)
  16.     {
  17.         ans = max( Solve(R,i,values,dp)+Solve(R,C-i,values, dp), ans);
  18.     }
  19.     if(values[R][C]!=0)ans = max(ans,values[R][C]);

  20.     dp[R][C] = ans;
  21.     return ans;
  22. }

  23. int main()
  24. {
  25.     int R, C;
  26.     cin >> R >> C;
  27.     int N;
  28.     cin >> N;

  29.     vector<vector<int>> values(201, vector<int>(201, 0));
  30.     vector<vector<int>> dp_table(R+1, vector<int>(C+1, -1));
  31.     for(int i=0; i<N; ++i)
  32.     {
  33.         int V, a, b;
  34.         cin >> V >> a >> b;
  35.         values[a][b] = max(values[a][b], V);
  36.         values[b][a] = max(values[b][a], V);
  37.     }
  38.     cout << Solve(R, C, values, dp_table);
  39.     return 0;
  40. }
  41. /*
  42. 6 6
  43. 1
  44. 5 1 1

  45. 3 5
  46. 4
  47. 10 2 2
  48. 2 3 1
  49. 5 3 4
  50. 1 3 1
  51. 详解vector二维数组的全部操作(超细图例解析!!!)
  52. */
複製代碼

作者: may    時間: 2024-11-3 22:42

  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <algorithm>
  4. #include <bits/stdc++.h>
  5. using namespace std;

  6. int main() {
  7.     int R, C, N;
  8.     cin >> R >> C >> N;

  9.     // 建立 DP 陣列並初始化為 0
  10.     vector<vector<int>> dp(R + 1, vector<int>(C + 1, 0));

  11.     // 讀取每個買家的需求,並更新 DP 陣列
  12.     for (int i = 0; i < N; ++i) {
  13.         int v, w, h;
  14.         cin >> v >> w >> h;
  15.         // 如果買家的需求可以放入板材中,則更新 dp[w][h] 和 dp[h][w]
  16.         if (w <= R && h <= C) dp[w][h] = max(dp[w][h], v);
  17.         if (h <= R && w <= C) dp[h][w] = max(dp[h][w], v);
  18.     }

  19.     // 動態規劃計算不同大小板材的最大收益
  20.     for (int w = 1; w <= R; w++) {
  21.         for (int h = 1; h <= C; h++) {
  22.             // 橫向切割
  23.             for (int i = 1; i < w; i++) {
  24.                 dp[w][h] = max(dp[w][h], dp[i][h] + dp[w - i][h]);
  25.             }
  26.             // 縱向切割
  27.             for (int j = 1; j < h; j++) {
  28.                 dp[w][h] = max(dp[w][h], dp[w][j] + dp[w][h - j]);
  29.             }
  30.         }
  31.     }

  32.     // 輸出結果,即為 R x C 板材的最大收益
  33.     cout << dp[R][C] << endl;

  34.     return 0;
  35. }
  36. /*
  37. 6 6
  38. 1
  39. 5 1 1

  40. 3 5
  41. 4
  42. 10 2 2
  43. 2 3 1
  44. 5 3 4
  45. 1 3 1
  46. 详解vector二维数组的全部操作(超细图例解析!!!)
  47. */
複製代碼





歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2