Chương trình C++ tìm tổng điểm tối đa từ dãy số tăng dần

Mô tả bài toán

Cho n, m và k bộ tư (a_i, b_i, c_i, d_i). Xét dãy dp gồm n số nguyên dương tăng chặt: 1 ≤ dp[1] < dp[2] < ... < dp[n] ≤ m. "Tally" = tổng d_i cho các i thỏa dp[b_i] - dp[a_i] = c_i. Tìm tally lớn nhất.

Ví dụ

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}. Đầu ra: 130.

Thuật toán (Backtracking + Pruning)

1. Vì n ≤ 10, có thể duyệt toàn bộ dãy tăng bằng đệ quy.
2. Hàm depthSearch(pos, last): thử gán dp[pos] = j từ last đến m.
3. Khi , tính tally và cập nhật kết quả lớn nhất.

Đoạn mã 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