Dynamic Programming

$闫氏dp分析法：\left\{\begin{aligned}& 状态表示(i,j)\left\{\begin{aligned}集合 ………………… …\\属性：(最大值,最小值,方案数…)\end{aligned}\right.\\& 状态计算：\left\{\begin{aligned}… \\… \\…\\\end{aligned}\right\}\end{aligned}\right.$

$dp$类型: 区间dp, 树形dp, 状压dp, 线性dp, 背包dp

背包问题: 01背包, 完全背包, 分组背包, 多重背包, 树上背包

背包问题名言:背包问题从容量开始找起, 什么东西有限就是容量

01背包的模型:

给定容量为m的背包, 有n个物品可选(完全背包每种物品有无限个), 已知重量v[i], 价值w[i], 求最大价值, 最小价值或方案数

状态:f[i][j]表示前i个物品可选, 背包容量为j的最大价值

状态转移: f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);

滚动数组优化

for (int i = 1; i <= n; i++)
    for (int j = m; j >= v[i]; j--) // 完全背包只变方向 v[i]->m
        f[j] = max(f[j], f[j - v[i]] + w[i]);

背包问题题目❤️

P1455 搭配购买

热身题(01背包+并查集)

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 $n$ 朵云，云朵已经被老板编号为 $1,2,3,…,n$，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入格式

第一行输入三个整数，$n,m,w$，表示有 $n$ 朵云，$m$ 个搭配和你现有的钱的数目。

第二行至 $n+1$ 行，每行有两个整数， $c_i,d_i$，表示第 $i$ 朵云的价钱和价值。

第 $n+2$ 至 $n+1+m$ 行 ，每行有两个整数 $u_i,v_i$。表示买第 $u_i$ 朵云就必须买第 $v_i$ 朵云,同理，如果买第 $v_i$ 朵就必须买第 $u_i$ 朵。

输出格式

一行，表示可以获得的最大价值。

样例 #1

样例输入 #1

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

样例输出 #1

1

提示

• 对于 $30\%$ 的数据，满足 $1 \le n \le 100$；
• 对于 $50\%$ 的数据，满足 $1 \le n, w \le 10^3$，$1 \le m \le 100$；
• 对于 $100\%$ 的数据，满足 $1 \le n, w \le 10^4$，$0 \le m \le 5 \times 10^3$。

分析

1. 钱数money有限;

2. 物品要搭配起来, 并查集解决“套餐”;

3. 对套餐跑01背包, 而不是云朵

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

const int N = 1e4 + 10;
int v[N], w[N];
int p[N];
int f[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}

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

    int n, k, m;
    cin >> n >> k >> m;

    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) p[i] = i;

    int a, b;
    while (k--)
    {   
        cin >> a >> b;

        a = find(a), b = find(b);

        if (a != b)
        {
            p[a] = b;
            v[b] += v[a]; // 价格要加在根节点上
            w[b] += w[a];
        }
    }

    for (int i = 1; i <= n; i++)
        if (p[i] == i)
            for (int j = m; j >= v[i]; j--)
                f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m];


    return 0;
}

CF507A Amr and Music

题目描述

给定$n$个物品，装进一个容量为$k$的背包，每个物品的价值为$1$，重量为$c[i]$。

求一种选物品的方案，要求所获得的价值最大（可以不装满背包），要求输出选的物品的编号（任意顺序，本题SPJ）

输入格式

第一行两个整数$n$，$k$。

第二行$n$个整数，表示每个物品的重量

输出格式

输出共两行。

第一行为所选的物品数量。

第二行为所选的物品的编号（任意排列，本题Special Judge）
for studying.

样例 #1

样例输入 #1

4 10
4 3 1 2

样例输出 #1

4
1 2 3 4

样例 #2

样例输入 #2

5 6
4 3 1 1 2

样例输出 #2

3
1 3 4

样例 #3

样例输入 #3

1 3
4

样例输出 #3

0

记录决策点, 也就是记录最优状态从哪里转移， 辅助状态记录决策点

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

const int N = 110, M = 1e4 + 10;
int v[N];
int f[M];
bool st[N][M]; // st[i][j] 表示物品i在容量为j时选或者不选

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> v[i];

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
            if (f[j - v[i]] >= f[j])
            {
                f[j] = f[j - v[i]] + 1;
                st[i][j] = true;
            }

    cout << f[m] << '\n';

    int i = n, j = m;
    while (i > 0 && j > 0)
    {
        if (st[i][j])
        {
            cout << i << ' ';
            j -= v[i];
        }

        i--;
    }


    return 0;
}

[ABC054D] Mixing Experiment

题目描述：

有 $N$ 个物体，第 $i$ 个物体含有 $a_i$ 质量的 A 元素 和 $b_i$ 质量的 B 元素，代价为 $c_i$ 。

问能否取若干个物体，使 A 元素与 B 元素质量之比为 $M_a : M_b$ ，并使代价最小。

输入格式:

第一行3个整数 $N ,M_a ,M_b$

下面 $N$ 行，每行3个整数 $a_i ,b_i ,c_i$

$ N $ $ M_a $ $ M_b $
$ a_1 $ $ b_1 $ $ c_1 $
$ a_2 $ $ b_2 $ $ c_2 $

$ : $
$ a_N $ $ b_N $ $ c_N $

输出格式：

若能满足条件则输出 最小代价。

否则输出 -1

数据范围：

• $1\le N\le 40$

• $1\le a_i,b_i\le 10$

• $1\le c_i\le 100$

• $1\le M_a,M_b\le 10$

• $gcd(M_a,M_b)=1$

• 输入都为整数。

样例 #1

样例输入 #1

3 1 1
1 2 1
2 1 2
3 3 10

样例输出 #1

3

样例 #2

样例输入 #2

1 1 10
10 10 10

样例输出 #2

-1

解析

1. 有2个背包容量, A元素的总量和B元素的总理;

2. 最小价值, 初始化memset

3. f[j][k]表示A元素总量不超过j且B元素总量不超过的最小价值

4. 枚举所有的dp[j][k], j : k == ma : mb, 取最小;

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

const int N = 410;
int a[N], b[N], c[N];
int f[N][N];

int main()
{
    int n, m1, m2;
    cin >> n >> m1 >> m2;

    int ma = 0, mb = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i];

        ma += a[i], mb += b[i];
    }

    memset(f, 0x3f, sizeof f);

    f[0][0] = 0;

    for (int i = 1; i <= n; i++)
        for (int j = ma; j >= a[i]; j--)
            for (int k = mb; k >= b[i]; k--)
                f[j][k] = min(f[j][k], f[j - a[i]][k - b[i]] + c[i]);

    int res = 1e9;
    for (int i = 1; i <= ma; i++)
        for (int j = 1; j <= mb; j++)
            if (i * m2 == j * m1)
                res = min(res, f[i][j]);

    if (res < 1e9) cout << res;
    else cout << -1;


    return 0;
}

[ABC118D] Match Matching

题面描述

在下列条件下，求正好用 $N$ 根火柴棒可以组成的最大整数：

• 整数中的每个数字都必须是数字 $A_1, A_2, …, A_M (1 \leq A_i \leq 9)$ 之一。
• 组成数字 $1, 2, 3, 4, 5, 6, 7, 8, 9$ 所用的火柴棒数量应分别为 $2, 5, 5, 4, 5, 6, 3, 7, 6$。

样例 #1

样例输入 #1

20 4
3 7 8 4

样例输出 #1

777773

样例 #2

样例输入 #2

101 9
9 8 7 6 5 4 3 2 1

样例输出 #2

71111111111111111111111111111111111111111111111111

样例 #3

样例输入 #3

15 3
5 4 6

样例输出 #3

654

简化题意: 给定n根木棍, 给定m个数码, 允许数码重复使用, 求木棍恰好用完能够拼成的最大整数.

分析:

1. 数位越多越好;

2. 把木棍的数量n当作容量, 数码当作物品, 数码使用的木棍当作重量, 价值是数位, 都是一;

3. 转换为完全被报道模型求最大价值;

4. 输出结果有两种策略, 一是记录决策点, 二是贪心选木棍少且数码大的

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

const int v[] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

const int N = 1e4 + 10;
int a[N];
int f[N];
int g[N], cnt;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) cin >> a[i];

    memset(f, 0xcf, sizeof f);

    f[0] = 0;
    for (int i = 1; i <= m; i++)
        for (int j = v[a[i]]; j <= n; j++)
            f[j] = max(f[j], f[j - v[a[i]]] + 1);

    sort(a + 1, a + m + 1);

    while (n)
    {
        int p = 0;
        for (int i = 1; i <= m; i++)
            if (n >= v[a[i]] && f[n - v[a[i]]] + 1 == f[n]) p = i;

        g[cnt++] = a[p];
        n -= v[a[p]];
    }

    for (int i = 0; i < cnt; i++) cout << g[i];


    return 0;
}

Thief in a Shop

1. 恰好需要放k个物品求价值的种类数;

2. 若取得价值val的最少物品数超过了k, 则val一定不可行;

3. 将所有物品的价值减去最小价值minx, 从而构造出价值为0的物品;

4. 当取得价值val的最少物品数不超过k， 则可以添加价值为0的物品凑够k个;

5. 最终的价值应该是枚举val并加上k*minx;

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

const int N = 1010;
int v[N];
int f[N * N];

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

    int n, k;
    cin >> n >> k;

    int maxx = 0, minx = 1e9;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];

        maxx = max(maxx, v[i]);
        minx = min(minx, v[i]);
    }

    maxx -= minx;

    for (int i = 1; i <= n; i++) v[i] -= minx;

    memset(f, 0x3f, sizeof f);

    f[0] = 0;
    for (int i = 1; i <= maxx * k; i++)
        for (int j = 1; j <= n; j++)
            if (v[j] <= i)
                f[i] = min(f[i], f[i - v[j]] + 1);

    for (int i = 0; i <= maxx * k; i++)
        if (f[i] <= k) cout << i + minx * k << ' ';


    return 0;
}

不开心的金明

$O(N * 300)$

1. 极差不超过3, 且物品数不超过100, 说明最贵的和最便宜的物品差价最多300;

2. 若最便宜的物品价格 v > 300, 省下的300元没有用处, 直接按重要度

3. 若最便宜的物品价格 v > 300, 省下300元没有用处, 直接按重要度从大到小贪心买;

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

const int N = 1e6;
int v[N], p[N];
int f[N];

bool cmp(int a, int b)
{
    return a > b;
}

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

    int n, m;
    cin >> n >> m;

    int minx = 1e9, maxx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i] >> p[i];

        minx = min(minx, v[i]);
        maxx = max(maxx, v[i]);
    }

    if (minx <= 300)
    {
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= v[i]; j--)
                f[j] = max(f[j], f[j - v[i]] + p[i]);

        cout << f[m];
    }
    else
    {
        sort(p + 1, p + n + 1, cmp);

        int res = 0;
        for (int i = 1; i <= m / maxx; i++) res += p[i];

        cout << res;
    }


    return 0;
}

区间$dp$

状态:f[i][j]表示将区间[i, j]合并, 拆分之后的答案的最小, 最大值, 或方案数

初始状态: dp[i][i] = …

状态转移:

for (int len = 2; len <= n; len++) // 区间长度
    for (int l = 1; l + len - 1 <= n; l++) // 枚举起点
    {
        int r = l + len - 1;

        for (int k = l; k < r; k++) // 断点
            ... ... ...
    }

识别区间$dp$

区间$dp$的最大特征是它的子问题是按照区间的长度划分

1. 拆分类, 合并类, 处理两端类

2. 从左往右或从右往左设定状态, 结果不同

模板题 P1775 石子合并（弱化版）

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

const int N = 310;
int s[N];
int f[N][N];

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

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];

        s[i] += s[i - 1];
    }

    memset(f, 0x3f, sizeof f);

    for (int i = 1; i <= n; i++) f[i][i] = 0;

    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;

            for (int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);

            f[l][r] += s[r] - s[l - 1];
        }

    cout << f[1][n];


    return 0;
}

P1040 [NOIP2003 提高组] 加分二叉树

某个点左边的序列一定是这个点的左子树，右边的序列，一定在这个点的右子树。

tr[i][j]表示[i, j]这段序列的根, 递归输出先序遍历.

注意初始化, f[i][i] = w[i]，当序列只有i 一个元素时，f[i][i]等于这个点本身.

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

const int N = 35;
int w[N];
int tr[N][N];
int f[N][N];

void dfs(int l, int r)
{
    if (l > r) return;

    int root = tr[l][r];

    cout << root << ' ';

    dfs(l, root - 1);
    dfs(root + 1, r);
}

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

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> w[i];

    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;

            if (len == 1)
            {
                f[l][r] = w[l];
                tr[l][r] = l;
            }
            else
                for (int k = l; k <= r; k++)
                {
                    int left = k == l ? 1 : f[l][k - 1];
                    int right = k == r ? 1 : f[k + 1][r]; 
                    int score = left * right + w[k];

                    if (f[l][r] < score)
                    {
                        f[l][r] = score;
                        tr[l][r] = k;
                    }
                }
        }

    cout << f[1][n] << '\n';

    dfs(1, n);


    return 0;
}

P4290 [HAOI2008] 玩具取名

1. 状态: f[i][j][c]表示区间[i, j]是否由字母c得到;

2. 答案: 判断 f[1][n][c], 其中c = [0, 3]

3. 转移:

f[l][r][c] |= f[l][k][a] && f[k + 1][r][b];

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

const int N = 210;
int w[5][20][2];
int cnt[5];
bool f[N][N][5];

int get(char c)
{
    if (c == 'W') return 1;
    if (c == 'I') return 2;
    if (c == 'N') return 3;
    if (c == 'G') return 4;
}

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

    cin >> cnt[1] >> cnt[2] >> cnt[3] >> cnt[4];

    string s;
    for (int i = 1; i < 5; i++)
        for (int j = 1; j <= cnt[i]; j++)
        {
            cin >> s;

            w[i][j][0] = get(s[0]);
            w[i][j][1] = get(s[1]);
        }

    string str;
    cin >> str;

    int m = str.size();
    for (int i = 0; i < m; i++)
    {
        int id = get(str[i]);

        f[i][i][id] = 1;
    }

    for (int len = 2; len <= m; len++)
        for (int l = 0; l + len - 1 < m; l++)
        {
            int r = l + len - 1;
            for (int c = 1; c <= 4; c++)
                for (int i = 1; i <= cnt[c]; i++)
                {
                    int a = w[c][i][0], b = w[c][i][1];

                    for (int k = l; k < r; k++)
                        f[l][r][c] |= f[l][k][a] && f[k + 1][r][b];
                }
        }

    if (f[0][m - 1][1]) cout << 'W';
    if (f[0][m - 1][2]) cout << 'I';
    if (f[0][m - 1][3]) cout << 'N';
    if (f[0][m - 1][4]) cout << 'G';
    if (!f[0][m - 1][1] && !f[0][m - 1][2] && !f[0][m - 1][3] && !f[0][m - 1][4]) cout << "The name is wrong!";


    return 0;
}

P8675 [蓝桥杯 2018 国 B] 搭积木

1. 考虑到要求方案数, 且上层的积木的受到下场影响, 应该是从下往上$dp$;

2. 同一层要连续摆放, 区间[i, j], 考虑区间$dp$;

3. 状态: f[l][i][j]表示从下往上第l层在区间[i, j]摆放积木的方案数;

4. 答案: $(\sum f[l][i][j])$ % $mod$

5. 转移:

if (s[l][j] - s[l][i - 1] == 0)
    for (int I = 1; I <= i; I++)
        for (int J = j; J <= m; J++)
            f[l][i][j] = (f[l][i][j] + f[l - 1][I][J]) % mod;

6. 初始: f[0][1][m] = 1;

7. 二维前缀和优化计算

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

typedef long long ll;

const ll N = 110, mod = 1e9 + 7;
ll s[N][N];
ll f[N][N];

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

    ll n, m;
    cin >> n >> m;

    string str;
    for (ll i = 1; i <= n; i++)
    {
        cin >> str;

        str = ' ' + str;

        for (ll j = 1; j <= m; j++)
        {
            s[i][j] = s[i][j - 1];

            if (str[j] == 'X') s[i][j]++;
        }
    } 

    ll res = 1;
    for (ll i = 1; i <= m; i++)
        for (ll j = m; j >= i; j--)
            if (s[n][j] == s[n][i - 1])
            {
                f[i][j] = f[i][j + 1] + f[i - 1][j] - f[i - 1][j + 1] + 1;
                res++;
            }

    for (ll k = n - 1; k; k--)
        for (ll i = 1; i <= m; i++)
            for (ll j = m; j >= i; j--)
                if (s[k][j] != s[k][i - 1]) f[i][j] = 0;
    else
    {
        res = (res + f[i][j]) % mod;

        f[i][j] = (f[i][j] + f[i - 1][j] + f[i][j + 1] - f[i - 1][j + 1]) % mod;
    }

    cout << res;


    return 0;
}

P3205 [HNOI2010] 合唱队

1. 决策点只有2个, 左端或者右端;

2. f[i][j][0/1]表示最终队形为区间[i, j]时, 且最后进去的是左端或者右端的人的方案数

3. 答案: $(f[1][n][0] + f[1][n][1])$ % mod

4. 转移:

if (h[i] < h[i + 1])
    f[i][j][0] += f[i + 1][j][0];

if (h[i] < h[j])
    f[i][j][0] == f[i + 1][j][1];

5. 初始化: f[i][i][0] = 1;

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

const int N = 2010, mod = 19650827;
int h[N];
int f[N][N][2];

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

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> h[i];

    for (int i = 1; i <= n; i++) f[i][i][0] = 1;

    for (int len = 1; len <= n; len++)
        for (int i = 1, j = i + len; j <= n; i++, j++)
        {   
            if (h[i] < h[j]) f[i][j][0] += f[i + 1][j][1];
            if (h[j] > h[i]) f[i][j][1] += f[i][j - 1][0];
            if (h[i] < h[i + 1]) f[i][j][0] += f[i + 1][j][0];
            if (h[j] > h[j - 1]) f[i][j][1] += f[i][j - 1][1];

            f[i][j][0] %= mod, f[i][j][1] %= mod;
        }

    cout << (f[1][n][0] + f[1][n][1]) % mod;


    return 0;
}

状态压缩$dp$

是一种关于$dp$表示形式的优化的动态规划

使用场景:

1. 需要状态压缩的数位较小;

2. 需要标记的状态通常只有两种;

3. 符合$dp$一般特征

常见的组合位运算的含义：

• 任何二进制数位&1得到它本身

• 任何二进制数位^1则取反

• 任何二进制数位&0则赋值为0

• 任何二进制数位|1则赋值为1

• (n>>k)&1取出二进制下n的第k位（从右往左）

• n&((1<<k)-1）取出二进制下n的右k位

• n^(1<<k)，将二进制下n的第k位取反

• n|(1<<k)，将二进制下n的第k位赋值1

• n&(~(1<<k)) 将二进制下n的第k位赋值0

• 去掉最后一位 • 10110 → 1011 • x >> 1

• 在最后添加0 • 1011 → 10110 • x << 1

注意这里的k可能和前面的有点歧义前面的是从0开始的, 这个是从1开始的~

• 在最后添加1 • 1011 → 10111 • (x << 1) | 1

• 右数第k位变成1 • 100011 → 100011 → 101011, k=4 • x | (1 << k - 1)

• 右数第k位变成0 • 101011 → 100011, k=4 • x & ~(1 << k - 1)

• 获取右数第k位 • 101011 → 1, k=4 • (x >> k - 1) & 1

• 截取最后k位 • 101011 → 1011, k=4 • x & ((1 << k) - 1)

• 把右边连续的1变成0 • 101011 → 101000 • x & x + 1

• 把右起第一个0变成1 • 101011 → 101111 • x | x + 1

• 把右边连续的0变成1 • 101000 → 101111 • x | x - 1

• 把右起第一个1变成0 • 101000 → 100000 • x & x - 1

• 取右边连续的1 • 101111 → 1111 • x ^ x + 1

例题:最短 Hamilton 路径

状态:f[i][j]表示当前到达点j且n个点的经过情况为二进制下的i时的最短路;

答案:f[(1 << n) - 1][n - 1];

转移:

for (int i = 0; i < (1 << n); i++) // 枚举所有可能经过的状态
        for (int j = 0; j < n; j++) // 当前点
            if (i >> j & 1)
                for (int k = 0; k < n; k++) // 上一步
                    if (i >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[k][j]);

初始化: f[1][0] = 0, 其余极大值

代码

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

const int N = 20, M = 1 << N;
int a[N][N];
int f[M][N];

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

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) cin >> a[i][j];

    memset(f, 0x3f, sizeof f);

    f[1][0] = 0;

    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            if (i >> j & 1)
                for (int k = 0; k < n; k++)
                    if (i >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[k][j]);

    cout << f[(1 << n) - 1][n - 1];


    return 0;
}