Trong bài toán này, ta cần tìm số lượng kỹ năng tối thiểu để hạ gục quái vật. Mỗi kỹ năng có sát thương cơ bản và khả năng gây sát thương gấp đôi khi máu quái vật không cao hơn ngưỡng nhất định. Mỗi kỹ năng chỉ dùng được một lần duy nhất.

Phân tích bài toán

Thông tin đầu vào gồm:

• n: số lượng kỹ năng (1 ≤ n ≤ 10)
• m: lượng máu ban đầu của quái vật
• Với mỗi kỹ năng: damage[i] là sát thương gốc, threshold[i] là ngưỡng máu để kích hoạt sát thương ×2

Vì n ≤ 10, ta có thể dùng phương pháp quay lui (backtracking) thử mọi thứ tự sử dụng kỹ năng. Tại mỗi bước, kỹ năng được chọn sẽ gây sát thương gấp đôi nếu máu quái vật hiện tại ≤ threshold, ngược lại gây sát thương thường.

Thiết kế thuật toán

Sử dụng đệ quy với các tham số:

• idx: chỉ số kỹ năng đang xét trong danh sách
• hp: máu còn lại của quái vật

Hàm đệ quy trả về số kỹ năng đã dùng nếu hạ gục được quái vật, hoặc giá trị vô cực nếu không thể.

Cài đặt Go

package main

import (
	"fmt"
)

const LIM = 11
const INF = 1 << 30

var dmg [LIM]int
var limit [LIM]int

func main() {
	// Dữ liệu test: số test case, mỗi case gồm n, m và n cặp (sát thương, ngưỡng)
	raw := []int{
		3,
		3, 100, 10, 20, 45, 89, 5, 40,
		3, 100, 10, 20, 45, 90, 5, 40,
		3, 100, 10, 20, 45, 84, 5, 40,
	}

	pos := 0
	tc := raw[pos]
	pos++

	for t := 0; t < tc; t++ {
		n := raw[pos]
		pos++
		hp := raw[pos]
		pos++

		for i := 0; i < n; i++ {
			dmg[i] = raw[pos]
			pos++
			limit[i] = raw[pos]
			pos++
		}

		res := solve(n, 0, hp)
		if res >= INF {
			fmt.Println(-1)
		} else {
			fmt.Println(res)
		}
	}
}

// Đệ quy tìm số kỹ năng ít nhất, idx là vị trí bắt đầu trong mảng
func solve(n, idx, hp int) int {
	if hp <= 0 {
		return 0 // Đã hạ gục, không cần thêm kỹ năng
	}
	if idx == n {
		return INF // Hết kỹ năng mà chưa hạ gục
	}

	best := INF
	for j := idx; j < n; j++ {
		// Đưa kỹ năng j lên vị trí idx để thử
		exchange(idx, j)

		var actual int
		if hp > limit[idx] {
			actual = dmg[idx] // Sát thương thường
		} else {
			actual = dmg[idx] * 2 // Sát thương nhân đôi
		}

		// Đệ quy với kỹ năng tiếp theo, cộng thêm 1 kỹ năng đã dùng
		val := 1 + solve(n, idx+1, hp-actual)
		if val < best {
			best = val
		}

		// Khôi phục trạng thái
		exchange(idx, j)
	}

	return best
}

func exchange(a, b int) {
	dmg[a], dmg[b] = dmg[b], dmg[a]
	limit[a], limit[b] = limit[b], limit[a]
}

Độ phức tạp thời gian là O(n!) do thử mọi hoán vị của kỹ năng. Không gian phụ O(n) cho ngăn xếp đệ quy.

Phiên bản Rust tương đương

const CAP: usize = 11;
const NO_ANSWER: i32 = i32::MAX / 2;

static mut PWR: [i32; CAP] = [0; CAP];
static mut GATE: [i32; CAP] = [0; CAP];

fn main() {
    let data = [3i32, 3, 100, 10, 20, 45, 89, 5, 40,
                3, 100, 10, 20, 45, 90, 5, 40,
                3, 100, 10, 20, 45, 84, 5, 40];

    let mut p: usize = 0;
    let cases = data[p] as usize;
    p += 1;

    for _ in 0..cases {
        let n = data[p] as usize;
        p += 1;
        let life = data[p];
        p += 1;

        unsafe {
            for i in 0..n {
                PWR[i] = data[p];
                p += 1;
                GATE[i] = data[p];
                p += 1;
            }
        }

        let ans = search(n, 0, life);
        if ans >= NO_ANSWER {
            println!("-1");
        } else {
            println!("{}", ans);
        }
    }
}

fn search(n: usize, pos: usize, life: i32) -> i32 {
    if life <= 0 {
        return 0;
    }
    if pos == n {
        return NO_ANSWER;
    }

    let mut optimal = NO_ANSWER;
    for j in pos..n {
        flip(pos, j);

        unsafe {
            let dealt = if life > GATE[pos] { PWR[pos] } else { PWR[pos] * 2 };
            let candidate = 1 + search(n, pos + 1, life - dealt);
            if candidate < optimal {
                optimal = candidate;
            }
        }

        flip(pos, j);
    }
    optimal
}

fn flip(a: usize, b: usize) {
    unsafe {
        let ta = PWR[a];
        PWR[a] = PWR[b];
        PWR[b] = ta;

        let tb = GATE[a];
        GATE[a] = GATE[b];
        GATE[b] = tb;
    }
}

Phiên bản C++ tương đương

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

const int SZ = 11;
int atk[SZ];
int trig[SZ];

int dfs(int n, int cur, int rem) {
    if (rem <= 0) return 0;
    if (cur == n) return 1e9;

    int res = 1e9;
    for (int j = cur; j < n; j++) {
        swap(atk[cur], atk[j]);
        swap(trig[cur], trig[j]);

        int hit = (rem > trig[cur]) ? atk[cur] : atk[cur] * 2;
        res = min(res, 1 + dfs(n, cur + 1, rem - hit));

        swap(atk[cur], atk[j]);
        swap(trig[cur], trig[j]);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests = 3;
    vector<pair<int,int>> dataset = {
        {3, 100}, {{10,20},{45,89},{5,40}},
        {3, 100}, {{10,20},{45,90},{5,40}},
        {3, 100}, {{10,20},{45,84},{5,40}}
    };

    // Xử lý từng test case...
    return 0;
}

Thuật toán trên tận dụng tính chất n nhỏ để duyệt toàn bộ không gian hoán vị, đảm bảo tìm được lời giải tối ưu.