home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

โปรแกรม C++ หาคะแนนสูงสุด (Tally) จากลำดับจำนวนเต็ม

กำหนดจำนวนเต็ม n, m และ k ตัวอันดับ (tuple) แต่ละอันดับมี 4 ค่า {a_i, b_i, c_i, d_i} พิจารณาลำดับ dp ขนาด n ที่เป็นจำนวนเต็มบวกและเพิ่มขึ้นอย่างเคร่งครัด (1 ≤ dp[1] < dp[2] < ... < dp[n] ≤ m) กำหนด "Tally" = ผลรวม d_i สำหรับทุก i ที่ dp[b_i] - dp[a_i] = c_i หา Tally สูงสุดที่เป็นไปได้

ตัวอย่าง: n=4, m=5, k=4, a={2,2,3,5}, b={4,3,4,6}, c={4,3,3,4}, d={110,20,20,40} ผลลัพธ์: 130

ขั้นตอนการแก้ปัญหา (Backtracking/DFS)

  1. สร้างอาร์เรย์ A, B, C, D จากอินพุต (ปรับดัชนีเป็น 0-based)
  2. ฟังก์ชัน depthSearch(c, l) สร้างลำดับ dp แบบrekursive:
    • ถ้า c == n คำนวณ Tally ของลำดับนี้ อัปเดตค่าสูงสุด
    • วน j = l ถึง m กำหนด dp[c] = j เรียก depthSearch(c+1, j)
  3. เริ่มต้นที่ depthSearch(0, 1)

ตัวอย่างโค้ด C++

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

int n, m, k, res = 0;
int A[100], B[100], C[100], D[100], dp[10];

void depthSearch(int c, int l) {
    if (c == n) {
        int total = 0;
        for (int i = 0; i < k; i++)
            if (dp[B[i]] - dp[A[i]] == C[i]) total += D[i];
        res = max(res, total);
        return;
    }
    for (int j = l; j <= m; j++) {
        dp[c] = j;
        depthSearch(c + 1, j);
    }
}

int solve(int a[], int b[], int c[], int d[]) {
    for (int i = 0; i < k; i++) {
        A[i] = a[i]; B[i] = b[i]; C[i] = c[i]; D[i] = d[i];
        A[i]--; B[i]--;
    }
    depthSearch(0, 1);
    return res;
}

int main() {
    n = 4, m = 5, k = 4;
    int a[] = {2, 2, 3, 5}, b[] = {4, 3, 4, 6}, c[] = {4, 3, 3, 4}, d[] = {110, 20, 20, 40};
    cout << solve(a, b, c, d);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, 5, 4, {2, 2, 3, 5}, {4, 3, 4, 6}, {4, 3, 3, 4}, {110, 20, 20, 40}

Output: 130