Sau khi học một số dạng quy hoạch động, V đã bị "tẩu hỏa nhập ma". Để giúp bạn mình sớm "bình thường" trở lại, T đã "tặng thêm" cho V `N` bài tập quy hoạch động. Biết rằng để giải bài tập thứ `i`, V cần `A_{ii}` phút, giải bài tập thứ `j` bằng cách tận dụng code đã sử dụng để giải bài tập thứ `i` V cần `A_{ij}` phút. Tuy nhiên, V "tẩu hỏa nhập ma" chứ không ngáo, V còn phải ôn các thuật toán khác để chuẩn bị thi Tin học trẻ khu vực nên V đã đặt `t` làm thời gian tối đa cho mấy "quà tặng" của T. V cần bạn tính xem mình có thể giải tất cả các bài trong thời gian ít nhất là bao lâu. Input: Dòng 1: `n, t`; Dòng 2 `->` n+1: Ma trận `A` (`NxN`). Output: Thời gian ít nhất hoặc NO. Ràng buộc: `n <= 16`, các giá trị còn lại không vượt quá `10^4`.

Tóm lại là V có tổng cộng N+1 bài tập quy hoạch động...

Thuật toán

Gọi $f(i_1, i_2, \ldots, i_x)$ là thời gian ít nhất để V giải được tất cả $x$ bài tập có số thứ tự $i_1, i_2, \ldots, i_x$.

Giả sử đến một lúc nào đó V đã giải được $x$ bài tập $i_1, i_2, \ldots, i_x$ $(x < n)$ mất lượng thời gian tối ưu $f(i_1, i_2, \ldots, i_x)$, và ta cần V giải thêm một bài tập có số thứ tự $j$ khác với các bài tập mà V đã giải được trước đó. Khi đó, V cần chọn phương án tối ưu trong hai phương án sau:

- Sử dụng lời giải của một bài trong các bài đã giải được để giải bài thứ $j$. Thời gian ít nhất V cần phải dùng để giải bài thứ $j$ theo phương án này là $min(A_{i_1,j},  A_{i_2, j}, \ldots, A_{i_x, j})$.

- Tự giải bài thứ $j$. V sẽ luôn mất thêm $A_{j,j}$ thời gian nếu sử dụng phương án này.

Như vậy, tổng thời gian tối ưu để V giải được các bài $i_1, i_2, \ldots, i_x$ rồi cuối cùng đến bài $j$ là:

$f_j(i_1, i_2, \ldots, i_x, j) = f(i_1, i_2, \ldots, i_x) + min(A_{i_1,j},  A_{i_2, j}, \ldots, A_{i_x, j}, A_{j,j})$

Để tìm $f(i_1, i_2, \ldots, i_x, j)$, ta sẽ tìm phương án tối ưu bằng cách thử từng bài làm bài hoàn thành cuối cùng.

$f(i_1, i_2, \ldots, i_x, j) = min(f_{i_1}(i_1, i_2, \ldots, i_x, j), f_{i_2}(i_1, i_2, \ldots, i_x, j), \ldots, f_j(i_1, i_2, \ldots, i_x, j)$

Với công thức truy hồi như trên và giới hạn $n$ bé, ta có thể sử dụng quy hoạch động bitmask để giải bài toán này trong $O(2^n \times n^2)$.

Code (C++)

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

int n,t,a[20][20],dp[1 << 17],prv,cur;

int main(){
    cin >> n >> t;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> a[i][j];
        }
    }
    dp[0] = 0;
    for(int mask=1;mask<(1 << n);mask++){
        dp[mask] = t + 1;
        for(int i=0;i<n;i++){
            if(mask & (1 << i)){
                prv = (mask ^ (1 << i));
                cur = a[i][i]; // tu giai bai i
                for(int j=0;j<n;j++){
                    if(prv & (1 << j)){
                        // lay bai j giai bai i
                        cur = min(cur, a[j][i]);
                    }
                }
                dp[mask] = min(dp[mask], dp[prv] + cur);
            }
        }
    }
    if(dp[(1 << n) - 1] > t){
        cout << "NO";
    }else{
        cout << dp[(1 << n) - 1];
    }
    return 0;
}