รถกระบะเชอร์รี่ใน C++

สมมติว่าเรามีตาราง N x N หนึ่งตาราง ซึ่งเต็มไปด้วยเชอร์รี่ แต่ละเซลล์มีหนึ่งในจำนวนเต็มที่เป็นไปได้ดังนี้ −

• 0 − แสดงว่าเซลล์ว่าง เราจึงสามารถผ่านได้
• 1 − ระบุว่าเซลล์มีเชอร์รี่ที่เราสามารถรับและผ่านไปได้
• -1 − บ่งบอกว่าเซลล์นั้นมีหนามที่ขวางทาง

เราต้องรวบรวมเชอร์รี่ให้ได้มากที่สุดโดยใช้กฎสองสามข้อนี้ -

• เริ่มจากตำแหน่ง (0, 0) และสิ้นสุดที่ (N-1, N-1) โดยเลื่อนไปทางขวาหรือลงผ่านเซลล์เส้นทางที่ถูกต้อง
• หลังจากไปถึงเซลล์ (N-1, N-1) ให้กลับไปที่ (0, 0) โดยเลื่อนไปทางซ้ายหรือขึ้นผ่านเซลล์เส้นทางที่ถูกต้อง
• เมื่อเราผ่านเซลล์พาธที่มีเชอร์รี่ เราจะหยิบมันขึ้นมาและเซลล์นั้นจะกลายเป็นเซลล์ว่าง (ค่าจะเป็น 0)
• หากไม่มีเส้นทางที่ถูกต้องระหว่าง (0, 0) และ (N-1, N-1) จะไม่สามารถเก็บเชอร์รี่ได้

ดังนั้นหากอินพุตเป็นเช่น −

ผลลัพธ์จะเป็น 5 โดยเริ่มจากตำแหน่ง (0, 0) และลงไป ลง ขวา ขวาเพื่อไปถึง (2, 2) ทริปเดียวนี้เก็บเชอร์รี่ 4 ลูก และเมทริกซ์ก็กลายเป็น

จากนั้นเราจะไปทางซ้าย ขึ้น ขึ้น ทางซ้ายเพื่อกลับ (0,0) เก็บเชอร์รี่เพิ่มอีก 1 ลูก จำนวนเชอร์รี่ที่รับทั้งหมดคือ 5 ผล

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ dir ขนาด:2 x 2 :={{1, 0}, {0, 1}}
• INF :=10^9
• กำหนดอาร์เรย์ dp ขนาด:51 x 51 x 51
• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้ r1, c1, c2, 2D array>&grid,
• n :=ขนาดของกริด, r2 :=r1 + c1 - c2, ret :=0
• m :=(ถ้า n ไม่ใช่ศูนย์ แสดงว่าขนาดของ grid[0] มิฉะนั้น 0)
• ถ้า r1 <0 หรือ c1 <0 หรือ r2 <0 หรือ c2 <0 หรือ r1>=n หรือ r2>=n หรือ c1>=m หรือ c2>=m แล้ว −
  • กลับ -INF
• ถ้า grid[r1, c1] เหมือนกับ -1 หรือ grid[r2, c2] เหมือนกับ -1 แล้ว −
  • กลับ -INF
• ถ้า r1 เหมือนกับ r2 และ c1 เหมือนกับ c2 และ r1 เหมือนกับ n - 1 และ c1 เหมือนกับ m - 1 −
  • กลับกริด[r1, c1]
• ถ้า dp[r1, c1, c2] ไม่เท่ากับ -1 แล้ว −
  • ส่งคืน dp[r1, c1, c2]
• ret :=ret + grid[r1, c1]
• ถ้า r1 เหมือนกับ r2 และ c1 เหมือนกับ c2 แล้ว:ไม่ต้องทำอะไร
• มิฉะนั้น
  • ret :=ret + grid[r2, c2]
• อุณหภูมิ :=-INF
• สำหรับการเริ่มต้น k :=0 เมื่อ k <2 อัปเดต (เพิ่ม k ขึ้น 1) ทำ −
  • อุณหภูมิ :=สูงสุดของอุณหภูมิและการแก้ปัญหา (r1 + dir[k, 0], c1 + dir[k, 1], c2 + 1, กริด)
  • อุณหภูมิ :=สูงสุดของอุณหภูมิและการแก้ปัญหา (r1 + dir[k, 0], c1 + dir[k, 1], c2, กริด)
• ผลตอบแทน dp[r1, c1, c2] =ret + อุณหภูมิ
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• เติม dp ด้วย -1
• ret :=แก้(0, 0, 0, ตาราง)
• คืนค่าสูงสุด 0 และ ret

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include using เนมสเปซ std;int dir[2][2] ={{1, 0}, {0, 1}};const int INF =1e9;class โซลูชัน {สาธารณะ:int dp[51][51][51]; int แก้ (int r1, int c1, int c2, vector >&grid){ int n =grid.size(); int r2 =r1 + c1 - c2; int ret =0; int m =n? กริด[0].size() :0; if(r1 <0 || c1 <0 || r2 <0 || c2 <0 || r1>=n || r2>=n || c1>=m || c2>=m) return -INF; if(grid[r1][c1] ==-1 || grid[r2][c2] ==-1) return -INF; if(r1 ==r2 &&c1 ==c2 &&r1 ==n - 1 &&c1 ==m - 1) return grid[r1][c1]; if(dp[r1][c1][c2] !=-1) ส่งคืน dp[r1][c1][c2]; ret +=grid[r1][c1]; if(r1 ==r2 &&c1 ==c2){ }else ret +=grid[r2][c2]; อุณหภูมิ int =-INF; สำหรับ(int k =0; k <2; k++){ temp =max(temp, แก้(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid)); temp =max(ชั่วคราว, แก้(r1 + dir[k][0], c1 + dir[k][1], c2, กริด)); } ส่งคืน dp[r1][c1][c2] =ret + temp; } int cherryPickup(vector>&grid) { memset(dp, -1, sizeof(dp)); int ret =แก้(0, 0, 0, กริด); ผลตอบแทนสูงสุด (0, ยกเลิก); }};main(){ โซลูชัน ob; เวกเตอร์<เวกเตอร์> v ={{0,1,-1},{1,0,-1},{1,1,1}}; cout <<(ob.cherryPickup(v));}

อินพุต

ผลลัพธ์

5