题谱

因为全是版子题，所以这里并没有详细写题解。

还是说，先要状态表示，再写出状态转移方程，同时，部分题记得初始化。

#include <iostream>
using namespace std;
const int N = 110;

int T;
int w[N][N];
int f[N][N];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        int r, c;
        scanf("%d %d", &r, &c);
        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++)
                scanf(" %d", &w[i][j]);

        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++)
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];

        printf("%d\n", f[r][c]);
    }
    return 0;
}

1018. 最低通行费 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;

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

int main()
{
    scanf("%d", &n);
    memset(f, 0x3f, sizeof(f));
    // 第一个点让他强制等于w[1][1];
    f[0][1] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf(" %d", &w[i][j]);

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

    printf("%d\n", f[n][n]);
    return 0;
}

1027. 方格取数 - AcWing题库

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 12;

// f[k][i1][i2]表示第一个点走到(i1,k-i1)第二个走到(i1,k-i2)所取得的最大数字和
int f[N * 2][N][N];
// w[i][j]是原图
int w[N][N];
int n;

int main()
{
    cin >> n;
    int a, b, c;
    while (cin >> a >> b >> c, a || b || c)
        w[a][b] = c;

    for (int k = 2; k <= n * 2; k++) // 控制走的步数一致
    {
        for (int i1 = 1; i1 < min(k, n + 1); i1++) // 即不用多搜,也保证能搜满全图
        {
            for (int i2 = 1; i2 < min(k, n + 1); i2++)
            {
                int j1 = k - i1, j2 = k - i2;

                // 如果走到一个点上,加一个就行
                int t = w[i1][j1];
                // 走的点不一样,两个都要加
                if (i1 != i2)
                    t += w[i2][j2];

                int &x = f[k][i1][i2];

                x = max(x, f[k - 1][i1 - 1][i2 - 1]);
                x = max(x, f[k - 1][i1][i2 - 1]);
                x = max(x, f[k - 1][i1 - 1][i2]);
                x = max(x, f[k - 1][i1][i2]);
                x += t;
            }
        }
    }

    printf("%d", f[n * 2][n][n]);

    return 0;
}

275. 传纸条 - AcWing题库

AcWing 275. 证明传纸条为何可以使用方格取数的代码 - AcWing

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 60;

// 表示学生矩阵有m行n列
int m, n;
// 同学的好心程度
int w[N][N];
int f[N + N][N][N];

int main()
{
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf(" %d", &w[i][j]);

    for (int k = 2; k <= m + n; k++)
    {
        for (int i1 = 1; i1 <= m; i1++)
        {
            for (int i2 = 1; i2 <= m; i2++)
            {
                int j1 = k - i1, j2 = k - i2;

                if (j1 < 1 || j1 > n || j2 < 1 || j2 > n)
                    continue;

                int t = w[i1][j1];
                if (i1 != i2)
                    t += w[i2][j2];

                int &x = f[k][i1][i2];
                x = max(x, f[k - 1][i1 - 1][i2 - 1]);
                x = max(x, f[k - 1][i1][i2 - 1]);
                x = max(x, f[k - 1][i1 - 1][i2]);
                x = max(x, f[k - 1][i1][i2]);
                x += t;
            }
        }
    }

    printf("%d", f[m + n][m][m]);
    return 0;
}