Hướng giải của Duyệt mua bánh

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Bình Minh

Do \(n <= 20\) nên ta hoàn toàn có thể dùng phương pháp duyệt nhị phân để duyệt tất cả các trường hợp đã cho của bài. Gọi f[i] là mảng để ta duyệt nhị phân 0/1. Nếu f[i] = 0 thì ta sẽ không ăn cái bánh mì ấy, ngược lại thì có. Số cách ăn được \(= dem\)

void dq(long long i)
{
    if(i < n)
    {
        for(int j = 0; j <= 1; j++)
        {
            f[i] = j;
            dq(i+1);
        }
    }
    if(i == n)
    {
        long long tong = 0;
        for(int j = 0; j < n; j++)
        {
            // cout << f[j] << ' ';
            if(f[j]) tong += a[j];
        }
        if(tong == k) dem++;
    }
}

Nhận xét