Title SOL-HSG12-ĐT-2122-B2.CauCa.pdf ✅

SOL CAUCA Hsg12-dongthap-2122 Cre : bach_21 ĐỀ BÀI Tổng quát
Đề yêu cầu chúng ta tính số lượng cá câu được ít nhất của một người qua các dữ liệu sau - Thời gian di chuyển qua các hồ câu cá : T[i] - Số lượng cá câu được trong 5 phút đầu của từng hồ : F[i] - Số lượng cá mất đi mỗi 5 phút : D[i] Ví dụ 4 1 5 10 15 2 3 4 5 1 1 1 1 Ta có thời gian di chuyển lần lượt là : 1 -> 2 : 5 phút , 2->3 : 10 phút 3->4 : 15 phút Số lượng cá câu được 5 phút đầu là : 2,3,4,5 Và cứ mỗi 5 phút ta mất đi 1 con Ta có 1 tiếng = 60 phút *Người đó phải xuất phát ở hồ 1 Vậy ta có phương án tối ưu là - Hồ 1 : không câu - Hồ 2 : câu 5 phút được 3 con mất 5 phút di chuyển (10 phút) - Hồ 3 : câu 10 phút được 7 con mất 10 phút di chuyển (20 phút) - Hồ 4 : câu 15 phút được 12 con mất 15 phút di chuyển (30 phút) Ta mất 10+20+30=60 phút = 1 tiếng câu được 3+7+12=22 đây là giải pháp tốt nhất Ta có 3 subtask ta sẽ cùng nhau đi giải từng subtask -Sub1 : N=1 -Sub2 : N=2 -Sub3 : Không có giới hạn **KIẾN THỨC CẦN CÓ - Quy hoạch động THUẬT TOÁN Sub1 : Cài đặt /Tiền xử lý O(H)
Thì sub1 này có rất nhiều cách giải khác nhau mình sẽ trình bày cách dùng tiền xử lý N=1 thì ta suy ra được rằng ta chỉ có thể câu M phút ở hồ 1 vậy giờ bài toán của chúng ta là trong M phút chúng ta câu được bao nhiêu con cá Vậy giờ ta có thể tính trước 5 phút trước câu được tổng bao nhiêu con cá và cộng với số cá 5 phút này mới câu được với công thức Max(0,f[i]-d[i]*(j/5-1) ) với i là số thứ tự hồ , j là số phút câu ở hồ đó CODE #include using namespace std; const int nmax=25; // gioi han N const int hmax=3e5+5; // gioi han H int n,h; int t[nmax],f[nmax],d[nmax]; int a[nmax][hmax]; signed main() { freopen("CAUCA.INP","r",stdin); freopen("CAUCA.OUT","w",stdout); cin >> n >> h; h=60*h; // doi gio sang phut for (int i=1;i> t[i]; } for (int i=1;i<=n;i++) { cin >> f[i]; } for (int i=1;i<=n;i++) { cin >> d[i]; } // doc du lieu for (int j=5;j<=h;j++) { a[1][j]=a[1][j-5]+max(0,f[1]-d[1]*((j/5)-1)); // a[1][j-5] tong so ca cau duoc 5 phut truoc } cout << a[1][h]; } Cre:Bach_21 CODE CHỈ MANG TÍNH CHẤT THAM KHẢO Sub2 : Vét cạn ( O(H) ) Ta chạy 1 vòng for là số phút câu ở hồ thứ 2 + số cá câu được ở hồ từ những phút còn lại CODE