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;

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

  22.     dp[R][C] = ans;
  23.     return ans;
  24. }

  26. int main()
  27. {
  28.     int R, C;
  29.     cin >> R >> C;
  30.     int N;
  31.     cin >> N;

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

  50. 3 5
  51. 4
  52. 10 2 2
  53. 2 3 1
  54. 5 3 4
  55. 1 3 1
  56. 详解vector二维数组的全部操作（超细图例解析！！！）
  57. */
複製代碼
作者: may    時間: 2024-11-3 22:42

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

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

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

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

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

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

  40.     return 0;
  41. }
  42. /*
  43. 6 6
  44. 1
  45. 5 1 1

  47. 3 5
  48. 4
  49. 10 2 2
  50. 2 3 1
  51. 5 3 4
  52. 1 3 1
  53. 详解vector二维数组的全部操作（超细图例解析！！！）
  54. */
複製代碼




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