24.6 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 กบกระโดดข้ามหิน

ระดับง่าย เวลาไม่เกิน 1 วินาที

ริมบึงมีก้อนหินวางเรียงเป็นแถวตรง เรียกว่าก้อนที่ 1 2 3 ไปเรื่อยๆ กบแต่ละตัวเริ่มอยู่บนฝั่ง ซึ่งนับเป็นตำแหน่ง 0 แต่ละครั้งกบกระโดดไปข้างหน้าได้ 1 2 หรือ 3 ก้อน และไม่เคยกระโดดถอยหลัง สองวิธีถือว่าต่างกันถ้าลำดับระยะที่กระโดดต่างกัน เช่น 1 แล้ว 3 กับ 3 แล้ว 1 เป็นคนละวิธี

คืนนี้มีกบ Q ตัว ตัวที่ j อยากไปหยุดที่ก้อนที่ N_j พอดี ให้ตอบทีละตัวว่ากบตัวนั้นมีวิธีกระโดดกี่วิธี คำตอบอาจใหญ่มาก ให้ตอบเป็นเศษจากการหารด้วย 1000000007

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 100000

บรรทัดที่สองมีจำนวนเต็ม Q ตัว คือ N₁ ถึง N_Q โดยที่ 1 ≤ N_j ≤ 1000000 อาจซ้ำกันและไม่ได้เรียงมา

ข้อมูลออก

Q บรรทัด บรรทัดที่ j คือจำนวนวิธีของกบตัวที่ j หารด้วย 1000000007 เหลือเศษเท่าไร

3
4 6 1

7
24
1

2
3 3

4
4

ดูคำใบ้

ให้ ways[i] คือจำนวนวิธีไปหยุดที่ก้อน i ครั้งสุดท้ายกบกระโดดมาจากก้อน i - 1 i - 2 หรือ i - 3 จึงบวกสามช่องนั้น กรณีฐานคือ ways[0] = 1 และระวังอย่าอ่านช่องติดลบ สามค่ารวมกันเกิน int ได้ ให้ mod ทุกครั้งที่บวก ส่วนที่ต้องคิดเพิ่มคือคำถามมีถึงแสนข้อ แต่ทุกข้อใช้ตารางเดียวกัน ถ้าเติมตารางใหม่ทุกคำถาม งานรวมคือ Q × N ถึง 10¹¹ ไม่ทัน ให้เติมตารางครั้งเดียวถึงก้อนที่ไกลที่สุดที่ถูกถาม แล้วตอบทุกคำถามด้วยการเปิดตาราง อ่านและพิมพ์เป็นแสนบรรทัด ใช้ ios::sync_with_stdio(false) กับ '\n'

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    vector<int> stones(q);
    int farthest = 0;
    for (int j = 0; j < q; j++) {
        cin >> stones[j];
        farthest = max(farthest, stones[j]);
    }
    vector<int> ways(farthest + 1, 0);
    ways[0] = 1;
    for (int i = 1; i <= farthest; i++) {
        long long total = 0;
        for (int jump = 1; jump <= 3 && jump <= i; jump++) {
            total += ways[i - jump];
        }
        ways[i] = total % MOD;
    }
    for (int j = 0; j < q; j++) {
        cout << ways[stones[j]] << '\n';
    }
    return 0;
}

ข้อ 2 ขึ้นบันไดให้เหนื่อยน้อยที่สุด

ระดับง่าย เวลาไม่เกิน 1 วินาที

บันไดขึ้นจุดชมวิวมี N ขั้น เรียกว่าขั้นที่ 1 ถึง N แต่ละขั้นสูงไม่เท่ากัน ขั้นที่ i ทำให้เหนื่อย c_i หน่วยเมื่อเหยียบ น้องเริ่มยืนที่พื้น ซึ่งไม่ทำให้เหนื่อย แต่ละก้าวขึ้นได้ 1 หรือ 2 ขั้น และต้องไปหยุดที่ขั้นที่ N ซึ่งต้องเหยียบด้วย ความเหนื่อยรวมคือผลรวมของ c_i ทุกขั้นที่เหยียบ ให้หาความเหนื่อยรวมที่น้อยที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ c₁ ถึง c_N โดยที่ 0 ≤ c_i ≤ 10⁹

ข้อมูลออก

ความเหนื่อยรวมที่น้อยที่สุด

6
3 8 2 7 1 9

5
1 5 100 5 1

ดูคำใบ้

ให้ tired[i] คือความเหนื่อยรวมน้อยที่สุดที่ไปหยุดที่ขั้น i ได้ ก้าวสุดท้ายมาจากขั้น i - 1 หรือ i - 2 จึงได้ c[i] + min(tired[i - 1], tired[i - 2]) กรณีฐานคือพื้นซึ่งไม่เหนื่อยเลย การเลือกก้าวไปขั้นที่เหนื่อยน้อยกว่าทีละก้าวแบบ greedy ผิดได้ ลองกับตัวอย่างที่สอง และผลรวมถึง 2 × 10¹⁴ ต้องใช้ long long

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> cost(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
    }
    vector<long long> tired(n + 1);
    tired[0] = 0;
    tired[1] = cost[1];
    for (int i = 2; i <= n; i++) {
        tired[i] = cost[i] + min(tired[i - 1], tired[i - 2]);
    }
    cout << tired[n] << '\n';
    return 0;
}

ข้อ 3 ตุ้มน้ำหนักน้อยที่สุด

ระดับง่าย เวลาไม่เกิน 1 วินาที

ห้องแล็บวิทยาศาสตร์มีตุ้มน้ำหนักสำหรับตาชั่งสองแขน N แบบ แบบที่ i หนัก w_i กรัม แต่ละแบบมีมากพอที่จะใช้กี่ลูกก็ได้ ครูต้องการวางตุ้มบนจานข้างเดียวให้หนักรวมพอดี X กรัม โดยใช้ตุ้มน้อยลูกที่สุด ให้หาว่าต้องใช้กี่ลูก ถ้าวางให้หนักพอดี X กรัมไม่ได้เลย ให้ตอบ -1

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ X คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100 และ 1 ≤ X ≤ 100000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ w₁ ถึง w_N ไม่ซ้ำกัน โดยที่ 1 ≤ w_i ≤ 100000

ข้อมูลออก

จำนวนตุ้มที่น้อยที่สุด หรือ -1 ถ้าทำไม่ได้

3 6
1 3 4

2 23
5 7

-1

4 11
9 6 5 1

ดูคำใบ้

ให้ fewest[x] คือจำนวนตุ้มน้อยที่สุดที่รวมได้ x กรัม ตุ้มลูกสุดท้ายหนักเท่าไรก็ได้ที่ไม่เกิน x กรณีฐานคือ fewest[0] = 0 ช่องอื่นเริ่มที่ INF ที่บวกหนึ่งแล้วไม่ล้น เช่น 10⁹ ถ้าจบแล้ว fewest[X] ยังเป็น INF ให้พิมพ์ -1 หยิบตุ้มหนักสุดก่อนแบบ greedy ผิดกับตัวอย่างที่สาม งานทั้งหมดคือ X × N ไม่เกิน 10⁷

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, target;
    cin >> n >> target;
    vector<int> weights(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    vector<int> fewest(target + 1, INF);
    fewest[0] = 0;
    for (int x = 1; x <= target; x++) {
        for (int w : weights) {
            if (w <= x) {
                fewest[x] = min(fewest[x], fewest[x - w] + 1);
            }
        }
    }
    if (fewest[target] == INF) {
        cout << -1 << '\n';
    } else {
        cout << fewest[target] << '\n';
    }
    return 0;
}

ข้อ 4 สวนมะม่วงกับรังผึ้ง

ระดับง่าย เวลาไม่เกิน 1 วินาที

สวนมะม่วงของโรงเรียนปลูกต้นมะม่วงเรียงเป็นแถวเดียว N ต้น ต้นที่ i มีผลสุก a_i ลูก นักเรียนจะเขย่าต้นมะม่วงเพื่อเก็บผล เขย่าต้นไหนก็ได้ผลสุกของต้นนั้นทั้งหมด แต่ต้นที่ปลูกติดกันมีรังผึ้งเกาะกิ่งที่พันกันอยู่ ถ้าเขย่าสองต้นที่ติดกัน ผึ้งจะแตกรัง จึงห้ามเขย่าต้นที่ i กับต้นที่ i + 1 ทั้งคู่ ให้หาว่าเก็บมะม่วงได้มากที่สุดกี่ลูก

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ a₁ ถึง a_N โดยที่ 0 ≤ a_i ≤ 10⁹

ข้อมูลออก

จำนวนมะม่วงที่เก็บได้มากที่สุด

7
20 50 30 10 60 40 30

3
50 60 50

ดูคำใบ้

ให้ best[i] คือมะม่วงมากที่สุดจากต้นที่ 1 ถึง i ต้นที่ i เก็บหรือไม่เก็บ ไม่เก็บได้ best[i - 1] เก็บได้ best[i - 2] + a[i] เลือกต้นที่มีผลมากที่สุดก่อนแบบ greedy ผิดกับตัวอย่างที่สอง ผลรวมถึง 2 × 10¹⁴ ต้องใช้ long long

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> fruits(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> fruits[i];
    }
    vector<long long> best(n + 1);
    best[0] = 0;
    best[1] = fruits[1];
    for (int i = 2; i <= n; i++) {
        best[i] = max(best[i - 1], best[i - 2] + fruits[i]);
    }
    cout << best[n] << '\n';
    return 0;
}

ข้อ 5 ช่วงที่ยอดขายดีที่สุด

ระดับกลาง เวลาไม่เกิน 1 วินาที

ร้านเครื่องเขียนหน้าโรงเรียนจดกำไรรายวันไว้ N วัน วันที่ i ได้กำไร a_i บาท วันไหนขาดทุนจะจดเป็นค่าติดลบ เจ้าของร้านอยากรู้ว่าช่วงวันติดกันช่วงไหนที่กำไรรวมมากที่สุด ช่วงต้องมีอย่างน้อยหนึ่งวัน

ถ้ามีหลายช่วงที่กำไรรวมเท่ากัน ให้ตอบช่วงที่เริ่มเร็วที่สุด ถ้ายังเริ่มวันเดียวกัน ให้ตอบช่วงที่จบเร็วที่สุด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ a₁ ถึง a_N โดยที่ -10⁹ ≤ a_i ≤ 10⁹

ข้อมูลออก

บรรทัดแรกคือกำไรรวมที่มากที่สุด บรรทัดที่สองคือวันเริ่มและวันจบของช่วงนั้น คั่นด้วยช่องว่าง

8
-3 5 -2 4 -6 3 2 -1

7
2 4

4
-5 -2 -8 -3

-2
2 2

ดูคำใบ้

ใช้ Kadane ในหน้า 24.4 คู่กับการจดวันเริ่มในหน้า 24.5 ให้ ending[i] คือผลรวมมากสุดของช่วงที่จบวันที่ i พอดี ถ้า ending[i - 1] ไม่ติดลบให้ต่อจากช่วงเดิม (ต่อเมื่อเป็น 0 ด้วย เพื่อให้เริ่มเร็วที่สุด) ไม่งั้นเริ่มใหม่ จดวันเริ่มไว้ทุกช่อง แล้วเปลี่ยนคำตอบเมื่อได้ผลรวมมากกว่า หรือได้เท่ากันแต่เริ่มเร็วกว่า ลองทุกคู่วันเริ่มวันจบเป็น 2 × 10¹⁰ คู่ ไม่ทัน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> profit(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> profit[i];
    }
    vector<long long> ending(n + 1);
    vector<int> start(n + 1);
    ending[1] = profit[1];
    start[1] = 1;
    int best_start = 1, best_end = 1;
    for (int i = 2; i <= n; i++) {
        if (ending[i - 1] >= 0) {
            ending[i] = ending[i - 1] + profit[i];
            start[i] = start[i - 1];
        } else {
            ending[i] = profit[i];
            start[i] = i;
        }
        long long best = ending[best_end];
        if (ending[i] > best || (ending[i] == best && start[i] < best_start)) {
            best_start = start[i];
            best_end = i;
        }
    }
    cout << ending[best_end] << '\n';
    cout << best_start << ' ' << best_end << '\n';
    return 0;
}

ระดับกลาง เวลาไม่เกิน 1 วินาที

ร้านเบเกอรี่ขายคุกกี้เป็นกล่อง มีกล่อง N ขนาด กล่องขนาดที่ i บรรจุคุกกี้ s_i ชิ้น ร้านไม่แบ่งขายเป็นชิ้น ห้องเรียนต้องการคุกกี้พอดี X ชิ้นสำหรับงานเลี้ยง จะซื้อกล่องแต่ละขนาดกี่กล่องก็ได้ รวมถึงไม่ซื้อเลย ถามว่ามีวิธีซื้อกี่วิธี สองวิธีถือว่าต่างกันเมื่อจำนวนกล่องของขนาดใดขนาดหนึ่งไม่เท่ากัน ลำดับที่หยิบกล่องไม่สำคัญ

คำตอบอาจใหญ่มาก ให้ตอบเป็นเศษจากการหารด้วย 1000000007

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ X คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100 และ 1 ≤ X ≤ 100000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ s₁ ถึง s_N ไม่ซ้ำกัน โดยที่ 1 ≤ s_i ≤ 100000

ข้อมูลออก

จำนวนวิธีซื้อ หารด้วย 1000000007 เหลือเศษเท่าไร ถ้าซื้อให้พอดีไม่ได้เลย ให้ตอบ 0

3 5
1 2 5

2 10
3 4

ดูคำใบ้

ข้อนี้นับแบบลำดับไม่สำคัญ ซื้อ 2 กล่องเล็กแล้ว 1 กล่องใหญ่ กับซื้อกล่องใหญ่ก่อน เป็นวิธีเดียวกัน ใช้ลูปนอกเป็นขนาดกล่อง ลูปในเป็นจำนวนชิ้นจากน้อยไปมาก ตามหน้า 24.3 ถ้าสลับลูปจะได้ 9 แทน 4 ในตัวอย่างแรก อย่าลืม mod ทุกครั้งที่บวก

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, target;
    cin >> n >> target;
    vector<int> sizes(n);
    for (int i = 0; i < n; i++) {
        cin >> sizes[i];
    }
    vector<int> ways(target + 1, 0);
    ways[0] = 1;
    for (int s : sizes) {
        for (int x = s; x <= target; x++) {
            ways[x] = (ways[x] + ways[x - s]) % MOD;
        }
    }
    cout << ways[target] << '\n';
    return 0;
}

ข้อ 7 ถอดรหัสตัวเลข

ระดับกลาง เวลาไม่เกิน 1 วินาที

ชมรมคอมพิวเตอร์ส่งข้อความลับกันด้วยรหัสง่ายๆ แทนตัวอักษร A ด้วย 1 B ด้วย 2 ไปจนถึง Z ด้วย 26 แล้วเขียนตัวเลขต่อกันโดยไม่เว้นวรรค เช่น BZ เขียนเป็น 226 ปัญหาคือ 226 อ่านกลับได้หลายแบบ คือ 2 2 6 (BBF) 22 6 (VF) และ 2 26 (BZ) ให้หาว่าตัวเลขที่ได้รับถอดกลับเป็นข้อความได้กี่แบบ

แต่ละตัวอักษรใช้ตัวเลขหนึ่งหรือสองหลักต่อกันเท่านั้น และต้องเป็นค่า 1 ถึง 26 ที่ไม่มีเลข 0 นำหน้า เช่น 06 ไม่ใช่ตัว F และ 0 ตัวเดียวไม่ใช่ตัวอักษรใด ถ้าถอดไม่ได้เลยให้ตอบ 0 คำตอบอาจใหญ่มาก ให้ตอบเป็นเศษจากการหารด้วย 1000000007

ข้อมูลเข้า

บรรทัดเดียว เป็นสตริงของตัวเลข 0 ถึง 9 ยาว L ตัว โดยที่ 1 ≤ L ≤ 1000000

ข้อมูลออก

จำนวนแบบที่ถอดได้ หารด้วย 1000000007 เหลือเศษเท่าไร

ดูคำใบ้

ให้ ways[i] คือจำนวนวิธีถอดรหัสตัวเลข i ตัวแรก ตัวอักษรสุดท้ายมาจากตัวเลขหนึ่งหลัก (ตัวที่ i ต้องไม่ใช่ 0) หรือสองหลัก (ตัวที่ i - 1 กับ i ต้องเป็น 10 ถึง 26) จึงบวก ways[i - 1] กับ ways[i - 2] เฉพาะกรณีที่ใช้ได้ กรณีฐาน ways[0] = 1 ระวังเลข 0 เช่น 06 ไม่ใช่ตัว F และ 30 ถอดไม่ได้เลย

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string code;
    cin >> code;
    int n = code.size();
    vector<int> ways(n + 1, 0);
    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (code[i - 1] != '0') {
            ways[i] = ways[i - 1];
        }
        if (i >= 2) {
            int two = (code[i - 2] - '0') * 10 + (code[i - 1] - '0');
            if (two >= 10 && two <= 26) {
                ways[i] = (ways[i] + ways[i - 2]) % MOD;
            }
        }
    }
    cout << ways[n] << '\n';
    return 0;
}

ข้อ 8 ใบเสร็จแสตมป์

ระดับกลาง เวลาไม่เกิน 1 วินาที

ร้านไปรษณีย์มีแสตมป์ N แบบ แบบที่ i ราคา p_i บาท แต่ละแบบมีกี่ดวงก็ได้ ลูกค้าต้องติดแสตมป์ให้ราคารวมพอดี X บาท ใช้น้อยดวงที่สุด และพนักงานต้องพิมพ์ใบเสร็จบอกว่าใช้แสตมป์ราคาอะไรบ้าง

ใบเสร็จเรียงราคาจากมากไปน้อย ถ้ามีหลายชุดที่ใช้จำนวนดวงน้อยที่สุดเท่ากัน ให้เทียบใบเสร็จของแต่ละชุดทีละตำแหน่งจากซ้าย แล้วเลือกชุดที่ตำแหน่งแรกที่ต่างกันมีราคามากกว่า เช่น ราคา 4 บาทด้วยแสตมป์ 1 2 3 บาท ใช้ 2 ดวงได้ทั้ง 3 1 และ 2 2 ต้องตอบ 3 1

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ X คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100 และ 1 ≤ X ≤ 100000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ p₁ ถึง p_N ไม่ซ้ำกันและไม่ได้เรียงมา โดยที่ 1 ≤ p_i ≤ 100000

ข้อมูลออก

ถ้าติดให้ราคาพอดี X บาทไม่ได้ ให้พิมพ์ -1 บรรทัดเดียว

ถ้าได้ บรรทัดแรกคือจำนวนดวงที่น้อยที่สุด K บรรทัดที่สองคือราคาของแสตมป์ K ดวง เรียงจากมากไปน้อย คั่นด้วยช่องว่าง

3 13
3 1 4

4
4 4 4 1

3 4
2 1 3

2
3 1

2 23
7 5

-1

ดูคำใบ้

เติม fewest[x] แบบข้อตุ้มน้ำหนักก่อน แล้วเดินย้อนจาก X ตามหน้า 24.5 ที่ x บาท ลองแสตมป์จากราคาแพงไปถูก เลือกดวงแรกที่ fewest[x - p] เท่ากับ fewest[x] - 1 แบบนี้ได้ดวงแพงที่สุดเท่าที่ยังใช้จำนวนดวงน้อยสุดได้ และดวงที่ได้ทีหลังไม่มีทางแพงกว่าดวงก่อน รายการจึงเรียงจากมากไปน้อยเองและตรงกับกติกาในโจทย์ ถ้าเก็บรายการทั้งชุดไว้ทุกช่องจะช้าและเปลืองหน่วยความจำเกินไป

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, target;
    cin >> n >> target;
    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }
    sort(prices.rbegin(), prices.rend());
    vector<int> fewest(target + 1, INF);
    fewest[0] = 0;
    for (int x = 1; x <= target; x++) {
        for (int p : prices) {
            if (p <= x) {
                fewest[x] = min(fewest[x], fewest[x - p] + 1);
            }
        }
    }
    if (fewest[target] == INF) {
        cout << -1 << '\n';
        return 0;
    }
    cout << fewest[target] << '\n';
    int x = target;
    bool first = true;
    while (x > 0) {
        for (int p : prices) {
            if (p <= x && fewest[x - p] == fewest[x] - 1) {
                cout << (first ? "" : " ") << p;
                first = false;
                x -= p;
                break;
            }
        }
    }
    cout << '\n';
    return 0;
}

ข้อ 9 กระโดดห้ามซ้ำระยะเดิม

ระดับยาก เวลาไม่เกิน 1 วินาที

ทีมกรีฑาซ้อมกระโดดขึ้นบันไดอัฒจันทร์ที่มี N ขั้น นักกีฬาเริ่มยืนที่พื้น ซึ่งนับเป็นขั้น 0 แต่ละครั้งกระโดดขึ้นได้ 1 2 หรือ 3 ขั้น และต้องไปหยุดที่ขั้น N พอดี โค้ชตั้งกติกาว่า ห้ามกระโดดระยะเดิมสองครั้งติดกัน เช่น กระโดด 2 ขั้นแล้วต้องตามด้วย 1 หรือ 3 ขั้นเท่านั้น ถามว่ามีวิธีกระโดดกี่วิธี สองวิธีถือว่าต่างกันถ้าลำดับระยะที่กระโดดต่างกัน

เช่น N = 4 มี 3 วิธี คือ 1 3, 3 1 และ 1 2 1 ส่วน 2 2 กับ 1 1 2 ผิดกติกา คำตอบอาจใหญ่มาก ให้ตอบเป็นเศษจากการหารด้วย 1000000007

ข้อมูลเข้า

บรรทัดเดียว มีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 1000000

ข้อมูลออก

จำนวนวิธี หารด้วย 1000000007 เหลือเศษเท่าไร

ดูคำใบ้

รู้แค่ว่าอยู่ขั้นไหนยังไม่พอ ต้องรู้ด้วยว่าก้าวล่าสุดยาวเท่าไร จึงจะรู้ว่าก้าวต่อไปห้ามยาวเท่าไร ให้สถานะเป็นสองค่า ways[i][j] คือจำนวนวิธีไปหยุดที่ขั้น i โดยก้าวสุดท้ายยาว j ขั้น ก้าวก่อนหน้าต้องไม่ยาว j จึงบวก ways[i - j][k] ทุก k ที่ไม่เท่ากับ j ส่วนก้าวแรกจากพื้นไม่มีก้าวก่อนหน้า ให้นับเป็นกรณีฐาน สถานะมี 3N ตัว งานต่อสถานะไม่เกิน 3

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main()
{
    int n;
    cin >> n;
    // ways[j][i] คือจำนวนวิธีไปหยุดที่ขั้น i โดยก้าวสุดท้ายยาว j ขั้น
    vector<vector<long long>> ways(4, vector<long long>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int jump = 1; jump <= 3 && jump <= i; jump++) {
            int from = i - jump;
            long long total = 0;
            if (from == 0) {
                total = 1;
            } else {
                for (int last = 1; last <= 3; last++) {
                    if (last != jump) {
                        total += ways[last][from];
                    }
                }
            }
            ways[jump][i] = total % MOD;
        }
    }
    cout << (ways[1][n] + ways[2][n] + ways[3][n]) % MOD << '\n';
    return 0;
}

ข้อ 10 ตัดวันแย่ทิ้งได้หนึ่งวัน

ระดับยาก เวลาไม่เกิน 1 วินาที

น้องจดคะแนนความพร้อมของตัวเองก่อนสอบแข่งขันทุกวัน N วัน วันที่ i ได้ a_i คะแนน วันที่ป่วยหรือนอนดึกคะแนนติดลบ ครูให้เลือกช่วงวันติดกันหนึ่งช่วงมาเขียนรายงาน คะแนนของช่วงคือผลรวมของทุกวันในช่วง และครูยอมให้ตัดวันใดวันหนึ่งในช่วงทิ้งได้ไม่เกินหนึ่งวัน แต่หลังตัดแล้วต้องเหลืออย่างน้อยหนึ่งวัน ให้หาคะแนนของช่วงที่มากที่สุดที่เป็นไปได้

เช่น คะแนน 6 -9 5 -1 4 เลือกทั้งห้าวันแล้วตัดวันที่ 2 ได้ 6 + 5 - 1 + 4 = 14 ซึ่งดีกว่าทุกช่วงที่ไม่ตัด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ a₁ ถึง a_N โดยที่ -10⁹ ≤ a_i ≤ 10⁹

ข้อมูลออก

คะแนนของช่วงที่มากที่สุด

5
6 -9 5 -1 4

3
-4 -2 -7

-2

ดูคำใบ้

เพิ่มข้อมูลลงในสถานะว่าตัดไปแล้วหรือยัง keep[i] คือผลรวมมากสุดของช่วงที่จบวันที่ i โดยยังไม่ตัด ซึ่งก็คือ Kadane ในหน้า 24.4 ส่วน cut[i] คือผลรวมมากสุดของช่วงที่จบวันที่ i และตัดไปแล้วหนึ่งวัน มาได้สองทาง คือตัดวันที่ i เอง ได้ keep[i - 1] หรือตัดวันก่อนหน้าไปแล้ว ได้ cut[i - 1] + a[i] คำตอบคือค่ามากสุดของทั้งสองตาราง ระวัง cut[1] ซึ่งตัดแล้วไม่เหลือวันไหนเลย

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

const long long NEG_INF = LLONG_MIN / 2;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> score(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    vector<long long> keep(n + 1), cut(n + 1);
    keep[1] = score[1];
    cut[1] = NEG_INF;
    long long answer = keep[1];
    for (int i = 2; i <= n; i++) {
        keep[i] = max(score[i], keep[i - 1] + score[i]);
        cut[i] = max(keep[i - 1], cut[i - 1] + score[i]);
        answer = max(answer, max(keep[i], cut[i]));
    }
    cout << answer << '\n';
    return 0;
}

24.6 แบบฝึกหัด

ข้อ 1 กบกระโดดข้ามหิน

ข้อมูลเข้า

ข้อมูลออก

ข้อ 2 ขึ้นบันไดให้เหนื่อยน้อยที่สุด

ข้อมูลเข้า

ข้อมูลออก

ข้อ 3 ตุ้มน้ำหนักน้อยที่สุด

ข้อมูลเข้า

ข้อมูลออก

ข้อ 4 สวนมะม่วงกับรังผึ้ง

ข้อมูลเข้า

ข้อมูลออก

ข้อ 5 ช่วงที่ยอดขายดีที่สุด

ข้อมูลเข้า

ข้อมูลออก

ข้อ 6 คุกกี้กล่อง

ข้อมูลเข้า

ข้อมูลออก

ข้อ 7 ถอดรหัสตัวเลข

ข้อมูลเข้า

ข้อมูลออก

ข้อ 8 ใบเสร็จแสตมป์

ข้อมูลเข้า

ข้อมูลออก

ข้อ 9 กระโดดห้ามซ้ำระยะเดิม

ข้อมูลเข้า

ข้อมูลออก

ข้อ 10 ตัดวันแย่ทิ้งได้หนึ่งวัน

ข้อมูลเข้า

ข้อมูลออก