202404潛力2-切割板材

may

https://leetcode.cn/problems/selling-pieces-of-wood/description/

切割板材 (Plate)
問題敘述
加工廠最近獲得了一片新的矩形板材，準備將其進行切割後再販售給不同買家。每位買家願意購買任意數量的板材，但該板材必須符合他指定的大小規格。 由於加工廠內設備的限制，切割板材時必須選定一片板材沿著垂直或水平方向一路切到底，不能在中途進行轉彎。舉例來說，如果想在長寬為 3*5 的板材上切出一個長寬為[2, 2]的正方形至少必須經過兩次切割，如下圖所示。

板材在不同方向的紋理是相同的，例如長寬為 4*6 的板材可以旋轉 90 度後作為長寬為 6*4 的板材。加工廠並沒有限制切割板材的次數，且板材經過切割後可以有剩餘沒有被賣出的部分。請寫一支程式幫忙計算一片板材經過切割後後可以獲得的最高營收。

評分說明
此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。 第一組（15分）：R = 1、C ≤ 10。 第二組（35分）：R = 1。 第三組（50分）：無特別限制。

may

1. //#include <iostream>
   
2. //#include <vector>
   
3. //#include <algorithm>
   
4. #include <bits/stdc++.h>
   
5. using namespace std;
   
6. 
   
7. int main() {
   
8.     int R, C, N;
   
9.     cin >> R >> C >> N;
   
10. 
    
11.     // 建立 DP 陣列並初始化為 0
    
12.     vector<vector<int>> dp(R + 1, vector<int>(C + 1, 0));
    
13. 
    
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.     }
    
22. 
    
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.     }
    
36. 
    
37.     // 輸出結果，即為 R x C 板材的最大收益
    
38.     cout << dp[R][C] << endl;
    
39. 
    
40.     return 0;
    
41. }
    
42. /*
    
43. 6 6
    
44. 1
    
45. 5 1 1
    
46. 
    
47. 3 5
    
48. 4
    
49. 10 2 2
    
50. 2 3 1
    
51. 5 3 4
    
52. 1 3 1
    
53. 详解vector二维数组的全部操作（超细图例解析！！！）
    
54. */

複製代碼

may

1. //#include<iostream>
   
2. //#include<vector>
   
3. //#include<algorithm>
   
4. //#include<utility>
   
5. #include<bits/stdc++.h>
   
6. using namespace std;
   
7. 
   
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]);
    
21. 
    
22.     dp[R][C] = ans;
    
23.     return ans;
    
24. }
    
25. 
    
26. int main()
    
27. {
    
28.     int R, C;
    
29.     cin >> R >> C;
    
30.     int N;
    
31.     cin >> N;
    
32. 
    
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
    
49. 
    
50. 3 5
    
51. 4
    
52. 10 2 2
    
53. 2 3 1
    
54. 5 3 4
    
55. 1 3 1
    
56. 详解vector二维数组的全部操作（超细图例解析！！！）
    
57. */

複製代碼