首页 algorithm 算法OJ Acwing

# 背包问题

# 01 背包

每个物品只能拿一次，求拿容量不超过 V 的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; 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;
}

# 完全背包

每个物品可以使用无数次，求拿容量不超过 V 的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N];
int f[N];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++) 
        for(int j = v[i]; j <= m; j++)//与01背包代码唯一不同的地方
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m];
    return 0;
}

# 多重背包

每个物品只能拿一次，每个物品最多有 s 件，求拿总容量不超过 V 的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
const int N = 12010;
int v[N], w[N];
int n, m;
int f[N];
int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; i++) 
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt++;
            v[cnt] = a * k, w[cnt] = b * k;
            s -= k, k *= 2;
        }
        if(s > 0)
        {
            cnt++;
            v[cnt] = a * s, w[cnt] = b * s;
        }
    }
    n = cnt;
    for(int i = 1; i <= n; 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;
}

# 分组背包

每组有若干个物品，每组只能选一个物品，求拿总容量不超过 V 的物品能得到的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N];
int v[N][N], w[N][N], s[N];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j++) cin >> v[i][j] >> w[i][j];
    }
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
            for(int k = 0; k <= s[i]; k++)
                if(v[i][k] <= j)    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m];
    return 0;
}

# 线性 Dp

# 数字三角形

方式一：从上往下 “走”

  1. 状态表示：f(i,j)f(i, j)
    • 集合：从(1,1)(1, 1) 到(i,j)(i, j) 的所有情况
    • 属性：MAX
  2. 状态计算
    • 这条路可以从f(i−1,j)f(i - 1, j) 走上来，也可以从f(i−1,j−1)f(i-1,j-1) 走上来
    • 所以，f(i,j)=max(f(i−1,j),f(i−1,j−1))+g(i,j)f(i,j)=max(f(i-1,j),f(i-1,j-1))+g(i,j)
  3. 答案：根据定义答案就是max(f[n][i])max(f[n][i])

注意：\color{Red}{注意：} 因为存在边界的情况，所以需要初始化为−∞-\infty

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int g[N][N], f[N][N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> g[i][j];
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i + 1; j++)
            f[i][j] = -1e9;
    f[1][1] = g[1][1];
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + g[i][j];
    int ans = -0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
        ans = max(ans, f[n][i]);
    cout << ans;
    return 0;
}

方式二：从下往上 “走”

  1. 状态表示：f(i,j)f(i,j)
    • 集合：从(i,j)(i,j) 到(1,1)(1,1)
    • 属性：MAX
  2. 状态计算
    • 这条路可以从f(i+1,j)f(i+1,j) 走上来，也可以从f(i+1,j+1)f(i+1,j+1) 走上来
    • f(i,j)=max(f(i+1,j),f(i+1,j+1))+g(i,j)f(i,j)=max(f(i+1,j),f(i+1,j+1))+g(i,j)
  3. 答案：f(1,1)f(1,1)

注意：\color{red}{注意：} 因为是从下往上的遍历，边界都包括在内，不用考虑边界情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int g[N][N], f[N][N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> g[i][j];
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + g[i][j];
    cout << f[1][1];
    return 0;
}

# 最长上升子序列

方式一：时间复杂度O(n2)O(n^2)

  1. 状态表示：f(i)f(i)
    • 集合：表示以w[i]w[i] 结尾的最大上升子序列
    • 属性：MAX
  2. 状态计算
    • 以 i 之前的、权值小于 i 的节点结尾的上升子序列的最大值 + 1
    • f(i)=max(f(j)+1)f(i) = max(f(j)+1)，其中w[j]<w[i],j<iw[j]<w[i],j<i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 1010;
int w[N], f[N];
int n, ans;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j <= i; j++)
            if(w[i] > w[j]) f[i] = max(f[i], f[j] + 1);//找到以比w[i]小的节点结尾的最长上升子序列
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}

方式二：时间复杂度O(nlogn)O(nlogn)

  1. 状态表示f(i)f(i)
    • 集合：表示长度为 i 的序列的最小结尾
    • 属性：序列中最后一个值的最小值
  2. 状态计算：
    • 如果w[i]w[i] 大于f(cnt)f(cnt)，直接加到 cnt 之后即可
    • 如果小于等于f(cnt)f(cnt)，找到 f 数组中第一个大于w[i]w[i] 的位置，进行替换
  3. 答案：f 数组的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int w[N], f[N];
int n, cnt;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    f[++cnt] = w[1];//初始化
    for(int i = 2; i <= n; i++)
    {
        if(w[i] > f[cnt]) f[++cnt] = w[i];
        else f[lower_bound(f + 1, f + cnt + 1, w[i]) - f] = w[i];
    }
    cout << cnt;
    return 0;
}

# 最长公共子序列

状态表示：f(i,j)f(i,j)

  1. 集合：表示 A 的前 i 个字符，B 的前 j 个字符的公共子序列的最长长度
  2. 属性：min

状态计算：

  1. a[i]==b[j]a[i] == b[j]，a[i],b[j]a[i],b[j] 都在，那么最长子序列的长度是前一个 + 1，即f[i−1][j−1]+1f[i-1][j-1]+1
  2. a[i]!=b[j]a[i]!=b[j]
    • a[i]a[i] 在，b[j]b[j] 不在：那就是算 A 的前 i 个字符，B 的前 i - 1 个字符的公共子序列的最长长度，即f[i][j−1]f[i][j - 1]
    • a[i]a[i] 不在，b[j]b[j] 在：那就是算 A 的前 i - 1 个字符，B 的前 i 个字符的公共子序列的最长长度，即f[i−1][j]f[i-1][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
char a[N], b[N];
int n, m;
int f[N][N];
int main()
{
    cin >> n >> m >> a + 1 >> b + 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m];
    return 0;
}

# 最短编辑距离

状态表示：f(i,j)f(i,j)

  1. 集合：表示A[1∼i]A[1\sim i] 转换到B[1∼j]B[1\sim j] 最少操作次数
  2. 属性：min

状态计算：

  1. 删：保证A[1∼i−1]A[1\sim i-1] 和B[1∼j]B[1\sim j] 匹配，即f[i−1][j]f[i-1][j]
  2. 替：保证A[1∼i−1]A[1\sim i-1] 和B[1∼j−1]B[1\sim j-1] 匹配，即f[i−1][j−1]f[i-1][j-1]
  3. 补：保证A[1∼i]A[1\sim i] 和B[1∼j−1]B[1\sim j-1] 匹配，即f[i][j−1]f[i][j-1]

总结：f[i][j]=min(f[i−1][j−1]+1,f[i−1][j]+1,f[i][j−1]+1)f[i][j] = min(f[i-1][j-1]+1,f[i-1][j]+1,f[i][j-1]+1)

初始化：

  1. f[0][i]f[0][i] 只能进行” 补 “操作
  2. f[i][0]f[i][0] 只能进行 “删” 操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
char a[N], b[N];
int n, m;
int f[N][N];

int main()
{
    cin >> n >> a + 1 >> m >> b + 1;
    memset(f, 0x3f, sizeof f);
    for(int i = 0; i <= n; i++) f[i][0] = i;
    for(int i = 0; i <= m; i++) f[0][i] = i;
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            //if(a[i] != b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
            //else f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
        
    cout << f[n][m];
    return 0;
}

# 区间 Dp

# 石子合并

状态表示：f(i,j)f(i, j)

  1. 集合：表示合并区间从 i 到 j 的最小代价
  2. 属性：min（记得初始化为∞\infty）

状态计算：

  1. 涉及区间和问题，使用前缀和

  2. f(i,j)=f(i,k)+f(k+1,j)+s[j]−s[i−1]f(i,j) = f(i,k)+f(k+1,j)+s[j]-s[i-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
const int N = 310;
int f[N][N], a[N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
    
    for(int len = 2; len <= n; len++)
    {
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            f[i][j] = 0x3f3f3f3f;
            for(int k = i; k <= j; k++)
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + a[j] - a[i - 1]);
            }
        }
    }
    cout << f[1][n];
    return 0;
}

# 计数类 Dp

# 整数划分

分析：可以看成完全背包问题的变式，把 1,2,3，……，n 看做 n 个物品，每个物品可以取无限次，问刚好取到体积为 n 的方案数

状态表示：f (i, j)

  1. 集合：表示前 i 个物品体积恰好为 j 的方案数
  2. 属性：所有相加

状态计算：

f(i,j)=f(i−1,j)+f(i−1,j−i)+f(i−1,j−2i),……f(i,j) = f(i-1,j)+f(i-1,j-i)+f(i-1,j-2i),……

f(i,j−i)=f(i−1,j−i)+f(i−1,j−2i)+f(i−1,j−3i)+……f(i,j-i)=f(i-1,j-i)+f(i-1,j-2i)+f(i-1,j-3i)+……

→\tof(i,j)=f(i−1,j)+f(i,j−i)f(i,j)=f(i-1,j)+f(i,j-i)

省去第一维：f(j)=f(j)+f(j−i)f(j)=f(j)+f(j-i)

初始化：

当一件都不选的时候方案数是 1，所以f[0]=1f[0]=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N];
int n;
int main()
{
    cin >> n;
    f[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            f[j] = (f[j] + f[j - i]) % mod;
    cout << f[n];   
    return 0;
}

# 数位统计 Dp

# 计数问题

分析：

  1. 将a∼ba\sim b 中1∼91\sim9 出现的次数转换成1∼a−11\sim a-1 和1∼b1\sim b 中每个数字出现的次数

  2. 对于求 abcdefg 中 t 在第 4 位出现的次数

    例子：1 <= xxxtyyy <= abcdefg

    1. xxx = 0 ~ abc - 1, yyy = 000 ~ 999，次数：abc * 1000
    2. xxx = abc
      1. d == t，yyy = 000 ~ efg ，次数：efg + 1
      2. d > t，yyy = 000 ~ 999，次数：10^3
      3. d < t，不成立

  3. 对于 t 是否等于 0，如果是 0，它不可能在首位，在算某一位数前面的 xxx 的时候，需要减去前面全是 0 的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 10;
int num[N];
int get_num(int l, int r)
{
    int res = 0;
    for(int i = l; i >= r; i--)
        res = res * 10 + num[i];
    return res;
}
int pow10(int x)
{
    int ans = 1;
    for(int i = 1; i <= x; i++)
        ans *= 10;
    return ans;
}
int work(int n, int x)
{
    if(n == 0) return 0;
    int len = 0, ans = 0;
    while(n)
    {
        num[++len] = n % 10;
        n /= 10;
    }
    if(x != 0)
    for(int i = len; i > 0; i--)
    { 
        if(i != len) ans += get_num(len, i + 1) * pow10(i - 1);
        if(num[i] == x) ans += get_num(i- 1, 1) + 1;
        else if(num[i] > x) ans += pow10(i - 1);
        else ans += 0;
    }
    else
    for(int i = len - 1; i > 0; i--)
    {
        ans += (get_num(len, i + 1) - 1) * pow10(i - 1);
        if(num[i] == x) ans += get_num(i- 1, 1) + 1;
        else if(num[i] > x) ans += pow10(i - 1);
        else ans += 0;
    }
    return ans;
}
int main()
{
    int a, b;
    while(scanf("%d%d", &a, &b) && a !=0 && b != 0)
    {
        if(a > b) swap(a, b);
        for(int i = 0; i <= 9; i++)
        {
            int ans = work(b, i) - work(a - 1, i);
            cout << ans << " ";
        }
        cout << '\n';
    }
    return 0;
}

# 状态压缩 Dp

充分利用二进制

# 蒙德里安的梦想

分析：一旦横着摆放的地方确定了，那么竖着摆放的地方就确定了。所以，最终的方案数就是横着摆放的方案数

状态表示：f(i,j)f(i,j)

  1. 我们按照列进行摆放，每一列由上一列更新
  2. 状态数：每一列的某行为 1，表示横放，并伸出到下一列；某行为 0，表示竖放或者由上一列伸出
  3. f(i,j)f(i,j) 表示第 i 行，状态数为 j 时的方案数；其中状态数 j 是 01 组成的二进制数

状态计算：

  1. f(i,j)=∑f(i−1,k)f(i,j)=\sum f(i-1,k) 表示第 i-1 列的所有合法方案数之和
  2. 初值：f[0][0]=1f[0][0] = 1，第 0 列没有横放的
  3. 答案：f[m][0]f[m][0]

判断是否合法：

  1. 上一列横放伸出的地方为 1，那么这一列的这一行只能是 0，即 j & k == 0
  2. 连续零的个数是偶数

提前初始化：

  • 根据上述两个规则初始化 st 数组，将所有状态是否合法列举出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
const int N = 12, M = 1 << N;
typedef long long ll;
ll f[N][M];
bool st[M];
int n, m;
ll work(int n, int m)
{
    //预处理
    for(int i = 0; i < 1 << n; i++)
    {
        st[i] = true;
        int cnt = 0;//记录每一列中连续0的个数
        for(int j = 0; j < n; j++)
        {
            if(i >> j & 1)
            {
                if(cnt & 1)
                {
                    st[i] = false;
                    break;
                }
            }
            else cnt++;
        }
        if(cnt & 1) st[i] = false;//判断前导零
    }
    //状态计算
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for(int i = 1; i <= m; i++)//枚举列
        for(int j = 0; j < 1 << n; j++)//枚举第i列的状态
            for(int k = 0; k < 1 << n; k++)//枚举第i-1列的状态
                if((j & k) == 0 && st[j | k]) f[i][j] += f[i - 1][k];
    return f[m][0];
}
int main()
{
    while(cin >> n >> m, n | m)
    {
        cout << work(n, m) << '\n';
    }
    return 0;
}

# 最短 Hamilton 路径

状态表示：f(state,j)f(state,j)

  1. 集合：终点为 j，路径状态为 state 的距离；一共有 20 个点，以二进制形式进行表示，共有2202^{20} 个情况
  2. 属性：min

状态计算：

  1. 0→j0\to j 可以转换成 0→k→j0\to k\to j

  2. 0→k0\to k 就是从 state 中减去 j 的路径情况

  3. 合法性判断：state 减去 j 之后的路径中第 k 位是否是 1，如果是则合法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << N;
int f[M][N], w[N][N];
int n;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> w[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 - (1 << j)) >> k) & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n - 1];          
    return 0;
}

# 树形 Dp

状态表示是f[N][2]f[N][2]

# 没有上司的舞会

状态表示：

  1. f(i,1)f(i,1) 表示在以 i 为根节点的子树中选择并且选择 i
  2. f(i,0)f(i,0) 表示在以 i 为根节点的子树中选择并且不选择 i

状态计算：(i,j)(i,j)

  1. 对于f(i,1)f(i,1)，显然不能选择 j，所以f(i,1)+=f(j,0)f(i,1)+=f(j,0)
  2. 对于f(i,0)f(i,0)，j 可选可不选，所以f(i,0)+=max(f(j,0),f(j,1))f(i,0)+=max(f(j,0),f(j,1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
const int N = 6010, M = 2 * N;
int head[M], ne[M], to[M], idx;
int happy[N];
bool fa[N];
int f[N][2];
int n;
void add(int a, int b)
{
    ne[idx] = head[a], to[idx] = b, head[a] = idx++;
}
void dfs(int r)
{
    f[r][1] += happy[r];
    for(int i = head[r]; i != -1; i = ne[i])
    {
        int j = to[i];
        dfs(j);
        f[r][1] += f[j][0];
        f[r][0] += max(f[j][0], f[j][1]);
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> happy[i];
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        fa[a] = b;
    }
    int root = 1;
    while(fa[root]) root++;
    dfs(root);
    cout << max(f[root][0], f[root][1]);
    return 0;
}

# 记忆化搜索

# 滑雪

状态表示：f(i,j)f(i,j)

  1. 集合：表示最终滑到(i,j)(i,j) 的一条路径

  2. 属性：max

状态计算：

  • 分成f(i−1,j)+1,f(i,j−1)+1,f(i+1,j)+1,f(i,j+1)+1f(i-1,j)+1,f(i,j-1)+1,f(i+1,j)+1,f(i,j+1)+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int n, m;
int g[N][N],f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y)
{
    int &v = f[x][y];//用v代替f[x][y]方便
    if(v != -1) return v;
    v = 1;//注意把v变成1
    for(int i = 0; i < 4; i++)
    {
        int xx = x + dx[i], yy = y + dy[i];
        if(xx > 0 && xx <= n && yy > 0 && yy <= m && g[x][y] > g[xx][yy])
            v = max(v, dp(xx, yy) + 1);
    }
    return v;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> g[i][j];
    int res = 0;
    memset(f, -1, sizeof f);        
    for(int i = 1; i <= n; i++)//因为每个点都可能是起点，所以都需要加入
        for(int j = 1; j <= m; j++)
            res = max(res, dp(i, j));
    cout << res ;
    return 0;
}