数字三角形模型

摘花生

题目描述

给定一个 n×m 的矩阵，起点位置在 (1,1)
，终点位置是 (n,m)接着给定该矩阵上，每个位置(x,y)上的物品的价值w现需要我们制定一个方案：
从起点出发，只能向右或向下走，如何走到终点，才能使经过的所有格子的物品总价值最大

思路

我们可以开二维数组f[i][j]来存储当前在i行j列的状态，用f[i][j]的值，表示从起点走到该点经过的所有格子的价值总和的最大值
则最终答案的状态就是f[n][m]
状态转移：由题知，f[i][j]只能由f[i-1][j]或f[i][j-1]得到

代码

DP：

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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int T;
int n, m;
int w[N][N];
int f[N][N];

int main()
{
    cin >> T;
    while (T -- )
    {
        memset(w, 0, sizeof w);
        memset(f, 0, sizeof f);
        cin >> n >> m;

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

        //dp
        for (int i = 1; i <= n; ++ i)
        {
            for (int j = 1; j <= m; ++ j)
            {
                f[i][j] = max(f[i][j - 1], f[i - 1][j]) + w[i][j];
            }
        }

        cout << f[n][m] << endl;
    }
    return 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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int T;
int n, m;
int w[N][N];
int f[N][N];

int dp(int x, int y)
{
    if (f[x][y] >= 0) return f[x][y];
    if (x < 1 || x > n || y < 1 || y > m) return f[x][y] = -INF;
    if (x == 1 && y == 1) return f[x][y] = w[x][y];

    int t = 0;
    t = max(t, dp(x - 1, y) + w[x][y]);
    t = max(t, dp(x, y - 1) + w[x][y]);
    return f[x][y] = t;
}
int main()
{
    cin >> T;
    while (T -- )
    {
        memset(w, 0, sizeof w);
        memset(f, -1, sizeof f);
        cin >> n >> m;

        for (int i = 1; i <= n; ++ i)
        {
            for (int j = 1; j <= m; ++ j)
            {
                cin >> w[i][j];
            }
        }
        cout << dp(n, m) << endl;
    }
    return 0;
}

最低同行费

题目描述

给定一个 n×n 的矩阵，让我们从左上角出发，最终走到右下角走过的方块数量的不能超过 2n−1个，求所有路线中，经过的方块的总价值最少的路线

思路

代码

Dp：

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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n;
int w[N][N];
int f[N][N];

int main()
{
    //input
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            cin >> w[i][j];
        }
    }

    //initialize
    memset(f, 0x3f, sizeof f);
    f[1][1] = w[1][1];

    //dp
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
            f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
        }
    }

    //output
    cout << f[n][n] << endl;

    return 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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n;
int w[N][N];
int f[N][N];

int dp(int x, int y)
{
    if (f[x][y] >= 0) return f[x][y];
    if (x == 1 && y == 1) return w[x][y];
    if (x < 1 || y < 1) return INF;

    int t = INF;
    t = min(t, dp(x - 1, y));
    t = min(t, dp(x, y - 1));
    return f[x][y] = t + w[x][y];
}
int main()
{
    //input
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            cin >> w[i][j];
        }
    }

    //dp
    memset(f, -1, sizeof f);
    cout << dp(n, n) << endl;

    return 0;
}

方格取数

题目描述

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0，某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

思路

k=i1+j1=i2+j2;