选做题1 采购

周末，小明要去超市采购。超市备货充足，每种商品的数量都足够。他需要n种商品，赋予每种商品一个权值，表示需要该商品的程度，权值越大，就越需要该商品。他的预算是M元，如何选择商品，才能最大程度满足他的需要。

输入格式:

第1行，两个整数n和M，分别代表商品数和预算，1≤n≤1000，0≤M≤400。

第2行，n个整数Di，用空格分隔，表示第i个商品的需要度，1≤i≤n，1≤Di≤100.

第3行，n个整数Pi，用空格分隔，表示第i个商品的价格，1≤i≤n，1≤Pi≤100.

输出格式:

第1行，1个整数，表示能得到的需要的最大程度。

第2行，n个整数，用空格分隔，表示每种商品的购买数量。如果方案不唯一，输出最靠左的。

输入样例:

在这里给出一组输入。例如：

3 10
4 5 6
3 4 5

输出样例:

在这里给出相应的输出。例如：

13
2 1 0

解法一：动态规划

完全背包问题，不用于一般的完全背包只需要求最大价值，这里还需要构造出最优解，即每个物品数量

• 初始化：dp[0][j]=0,j<w[0]
• 边界条件：第一个物品的处理for (int j = w[0]; j <= M; j++)dp[0][j] = dp[0][j - w[0]] + value[0];
• 状态转移方程dp[i][j] = w[i] > j ? dp[i - 1][j] : max(dp[i - 1][j], dp[i][j - w[i]] + value[i]);

[!caution]

构造最优解，并且尽量选择靠左的物品

• 根据dp数组的定义，dp[i][j]表示在容量为j的情况下，前i（包括i)个物品的最大可获得价值，所以当dp[i][j]!=dp[i-1][j]时，表示肯定取了当前物品，反之跳到下一个物品
• 所以从后往前遍历，当dp[i][j]!=dp[i-1][j]，count[i]++,j-=w[i]反之处理i-1
• 最后在剩余j容量的情况下处理第一个物品count[0]=j/w[0]

#include<iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;


int main()
{
    int n, M;
    cin >> n >> M;
    vector<vector<int>> dp(n, vector<int>(M + 1, 0));
    vector<int> w(n), value(n);
    for (int i = 0; i < n; i++)cin >> value[i];
    for (int i = 0; i < n; i++)cin >> w[i];

    for (int j = w[0]; j <= M; j++)dp[0][j] = dp[0][j - w[0]] + value[0];

    for (int i = 1; i < n; i++)
        for (int j = 0; j <= M; j++)
            dp[i][j] = w[i] > j ? dp[i - 1][j] : max(dp[i - 1][j], dp[i][j - w[i]] + value[i]);

    cout << dp[n - 1][M] << endl;;

    vector<int> count(n, 0);
    int cur_v = M;
    for(int i=n-1;i>=1;i--)
    {
        // 如果当前状态必须选物品i，则选一个
        while (cur_v >= w[i])
        {
            if (dp[i][cur_v] != dp[i - 1][cur_v]) {
                count[i]++;
                cur_v -= w[i];
            }
            else break;
        }
    }

    if (cur_v >= w[0]) {
        count[0] = cur_v / w[0];
        cur_v %= w[0];
    }
    for (int i = 0; i < n; i++) {
        cout << count[i];
        if (i < n - 1)cout << " ";
    }
    cout << endl;
    return 0;
}

• 因为需要构造最优解，所以无法优化空间为滚动数组或者一维数组，但是可以利用额外的一维数组记录选择

#include<iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;


int main()
{
    int n, M;
    cin >> n >> M;
    vector<int> dp(M + 1, 0),last(M+1,-1);
    vector<int> w(n), value(n);
    for (int i = 0; i < n; i++)cin >> value[i];
    for (int i = 0; i < n; i++)cin >> w[i];


    for (int i = 0; i < n; i++)
        for (int j = w[i]; j <= M; j++)
            if(dp[j]<dp[j-w[i]]+value[i]){
                dp[j]=dp[j-w[i]]+value[i];
                last[j]=i;
            }

    cout << dp[M] << endl;;

    vector<int> count(n, 0);
    int cur_v=M;
    while(cur_v>0)
    {
        if (last[cur_v] != -1)
        {
            count[last[cur_v]]++;
            cur_v -= w[last[cur_v]];
        }
        else
        {
            break;
        }
    }

    for (int i = 0; i < n; i++) {
        cout << count[i];
        if (i < n - 1)cout << " ";
    }
    cout << endl;
    return 0;
}

解法二：记忆化搜索

• 和解法一不同处在于dp数组的构造
• 这里采用自顶而下的构造

#include<iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
vector<vector<int>> dp;
vector<int> w, value;
int dfs(int i,int j)
{
    if(i==0)return dp[i][j]=(j/w[0])*value[0];
    if(dp[i][j]!=-1)return dp[i][j];
    return dp[i][j]=j<w[i]?dfs(i-1,j):max(dfs(i-1,j),dfs(i,j-w[i])+value[i]);
}

int main()
{
    int n, M;
    cin >> n >> M;
    dp.resize(n, vector<int>(M + 1, -1));
    w.resize(n);
    value.resize(n);
    for (int i = 0; i < n; i++)cin >> value[i];
    for (int i = 0; i < n; i++)cin >> w[i];

    for (int j = w[0]; j <= M; j++)dp[0][j] = dp[0][j - w[0]] + value[0];
    dfs(n-1,M);
    cout << dp[n - 1][M] << endl;;

    vector<int> count(n, 0);
    int cur_v = M;
    for(int i=n-1;i>=1;i--)
    {
        // 如果当前状态必须选物品i，则选一个
        while (cur_v >= w[i])
        {
            if (dp[i][cur_v] != dp[i - 1][cur_v]) {
                count[i]++;
                cur_v -= w[i];
            }
            else break;
        }
    }

    if (cur_v >= w[0]) {
        count[0] = cur_v / w[0];
        cur_v %= w[0];
    }
    for (int i = 0; i < n; i++) {
        cout << count[i];
        if (i < n - 1)cout << " ";
    }
    cout << endl;
    return 0;
}

必做题 最优二分检索树

一个集合有n个标识符。设该集合递增有序，标识符编号从1到n。统计一段时间内对该集合的查找操作，得知查找第i个标识符的次数是Pi(1≤i≤n) ；查找不在该集合的标识符（即未找到）的情况，可分为n+1种情形：小于第1个标识符、在第i个标识符和第i+1个标识符之间(1≤i≤n-1)，大于第n个标识符，每种情形的次数是Qi(0≤i≤n)。

请你构造一棵二分检索树，使这段时间的所有查找操作的平均检索次数最小，并输出这棵树的先根序列。如果有多棵树满足条件,输出根接点编号最小的那一棵。

输入格式:

第1行，一个整数n，表示标识符的个数，1≤n≤5000。

第2行，n个整数Pi，Pi表示查找第i个标识符的次数，0≤Pi≤10。

第3行，n+1个整数Qi，Qi表示未找到的第i种情形的次数，0≤Qi≤10。

输出格式:

n行，表示所求二叉树的先根序列，每个结点的编号占一行。

输入样例:

在这里给出一组输入。例如：

4
3 3 1 1
2 3 1 1 1

输出样例:

在这里给出相应的输出。例如：

2
1
3
4

解法一：动态规划

• 具体详见最优二叉搜索树
• 当 j=i−1 时，子问题只包含虚关键字 di−1 ，搜索的期望代价为 e[i,i−1]=qi−1 。
• 当 j≥i 时，设子树根结点关键字为 kr ，左子树包含关键字 ki,…,kr−1 ，右子树包含关键字 kr+1,…,kj 。
• 所以状态转移：e[i][j]=min(e[i][r-1]+e[r+1][j]+w[i][j])，i<=r<=j同时记录root[i][j]即在[i,j]选的根节点

#include<iostream>
#include <vector>
#include<climits>
#include <algorithm>
#include <functional>
using namespace std;

//前序遍历
void dfs(int i,int j,const vector<vector<int>>& root) {
    if (i > j)return;
    cout << root[i][j] << endl;
    dfs(i, root[i][j] - 1,root);
    dfs(root[i][j] + 1, j,root);
}

int main()
{
    int n;
    cin >> n;
    vector<int> p(n), q(n + 1);
    for (int i = 0; i < n; i++)cin >> p[i];
    for (int i = 0; i <= n; i++)cin >> q[i];

    vector<vector<int>> e(n + 2, vector<int>(n + 1,INT_MAX)), w(n + 2, vector<int>(n + 1,0)), root(n + 1, vector<int>(n + 1,0));
    for (int i = 1; i <= n+1; i++) {
        e[i][i - 1] = w[i][i - 1] = q[i - 1];
    }

    for (int len = 1; len <= n; len++)
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            w[i][j] = w[i][j - 1] + p[j-1] + q[j];

            int left = (len == 1) ? i : root[i][j - 1];
            int right = (len == 1) ? i : root[i + 1][j];
            for (int r = left; r <= right; r++)
            {
                int t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if (t < e[i][j]) {
                    e[i][j] = t;
                    root[i][j] = r;
                }
            }
        }
    dfs(1, n, root);
    return 0;
}

选做题2 传纸条问题

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。

纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，如果他在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

此外，全班每个同学愿意帮忙的好心程度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 0 表示），可以用一个 0-100 的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度的和最大。

现在，请你帮助小渊和小轩找到这样的两条路径。

输入格式:

第一行有 2 个用空格隔开的整数 m 和 n，表示班里有 m 行 n 列（1<=m,n<=50）。

接下来的 m 行是一个 m*n 的矩阵，矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度。每行的 n 个整数之间用空格隔开。

输出格式:

一个整数，表示来回两条路上参与传递纸条的学生 的好心程度之和的最大值。

输入样例:

3 3
0 3 9
2 8 5
5 7 0

输出样例:

在这里给出相应的输出。例如：

34

解法一：暴力递归

• 利用回溯法搜索每一条路径，但是超时

#include<iostream>
#include <vector>
#include<climits>
using namespace std;

int ans = INT_MIN;
int m, n;

void dfs1(int i, int j, const vector<vector<int>>& g, vector<vector<int>>& vis, int now);

void dfs0(int i, int j, const vector<vector<int>>& g, vector<vector<int>>& vis, int now) {
    // 到达终点时开始回程
    if (i == m - 1 && j == n - 1) {
        dfs1(i, j, g, vis, now);
        return;
    }

    // 向下移动
    if (i < m - 1 && !vis[i+1][j]) {
        vis[i+1][j] = 1;
        dfs0(i + 1, j, g, vis, now + g[i+1][j]); // 累加新位置的值
        vis[i+1][j] = 0;
    }

    // 向右移动
    if (j < n - 1 && !vis[i][j+1]) {
        vis[i][j+1] = 1;
        dfs0(i, j + 1, g, vis, now + g[i][j+1]); // 累加新位置的值
        vis[i][j+1] = 0;
    }
}

void dfs1(int i, int j, const vector<vector<int>>& g, vector<vector<int>>& vis, int now) {
    // 成功返回起点，更新最大价值
    if (i == 0 && j == 0) {
        ans = max(ans, now);
        return;
    }

    // 向上移动（回程）
    if (i > 0) {
        int ni = i-1, nj = j;
        // 特殊处理起点位置
        if (ni == 0 && nj == 0) {
            dfs1(ni, nj, g, vis, now); // 不累加起点值（已累加过）
        }
        // 处理其他位置
        else if (!vis[ni][nj]) {
            vis[ni][nj] = 1;
            dfs1(ni, nj, g, vis, now + g[ni][nj]); // 累加新位置的值
            vis[ni][nj] = 0;
        }
    }

    // 向左移动（回程）
    if (j > 0) {
        int ni = i, nj = j-1;
        // 特殊处理起点位置
        if (ni == 0 && nj == 0) {
            dfs1(ni, nj, g, vis, now); // 不累加起点值（已累加过）
        }
        // 处理其他位置
        else if (!vis[ni][nj]) {
            vis[ni][nj] = 1;
            dfs1(ni, nj, g, vis, now + g[ni][nj]); // 累加新位置的值
            vis[ni][nj] = 0;
        }
    }
}

int main() {
    cin >> m >> n;
    // 创建正确大小的网格和访问标记数组
    vector<vector<int>> g(m, vector<int>(n, 0));
    vector<vector<int>> vis(m, vector<int>(n, 0));

    // 读取网格数据
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j];

    // 特殊情况处理：1x1网格
    if (m == 1 && n == 1) {
        cout << g[0][0] << endl; // 起点/终点值
        return 0;
    }

    // 初始化：标记起点并开始DFS
    vis[0][0] = 1;
    dfs0(0, 0, g, vis, g[0][0]); // 起点值已累加

    // 输出最大价值
    cout << ans << endl;
    return 0;
}

解法二：动态规划

• 首先是四维dp数组
• 从上方和从下方传纸条，为了方便，我们相当于从左上角连续传两张纸条，路径不重复，效果相同
• 定义 dpi,j,k,l 为第一遍走到了 (i,j)，第二遍走到了 (k,l) 时的最大值
• 同时为了防止边界讨论，增加数组长度
• 状态转移：dp[i][j][k][l] = max(dp[i - 1][j][k - 1][l], dp[i - 1][j][k][l - 1], dp[i][j - 1][k][l - 1], dp[i][j - 1][k - 1][l]) + g[i][j]+(i==k&&j==l?0:g[k][l]);两个点是由两个路径转过来的，每个点可以是左边或上边的状态转移过来，那两个点就要求出四种情况的最大值
• 有一种两个点的位置相同的情况，所以这种情况我们只能加一次，即两条路径在 (i,j) 和 (k,l) 处重合（即 i == k && j == l），则需要减去重复计算的 g[i][j]

#include<iostream>
#include <vector>
#include<climits>
#include <algorithm>
#include <functional>
using namespace std;

int dp[51][51][51][51] = { 0 };


int main()
{
    int m, n;
    cin >> m >> n;
    if (m == 1 && n == 1) {
        cout << 0;
        return 0;
    }
    vector<vector<int>> g(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= m; k++)
                for (int l = 1; l <= n; l++)
                {
                    dp[i][j][k][l] = max(max(dp[i - 1][j][k][l - 1], dp[i - 1][j][k - 1][l]), max(dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1])) + g[i][j] + g[k][l];
                    if (i == k && j == l)dp[i][j][k][l] -= g[i][j];
                }
    cout << dp[m][n][m][n]<<endl;
    return 0;
}

• 优化遍历，因为两条路径不相交，只转移 k>i,t<j 的情况
• 因此也不再需要特判i == k && j == l
• 同时最后因为不会遍历到dp[m][n][m][n]所以返回dp[m-1][n][n][m-1]
• 但是不知道为什么无法通过pta测试，但是洛谷可以通过

#include<iostream>
#include <vector>
#include<climits>
#include <algorithm>
#include <functional>
using namespace std;

int dp[51][51][51][51] = { 0 };


int main()
{
    int m, n;
    cin >> m >> n;
    vector<vector<int>> g(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
 // 特殊情况处理：m == 1 或 n == 1
    if (m == 1 || n == 1) {
        int max_sum = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                max_sum += g[i][j];
        cout << max_sum << endl;
        return 0;
    }


    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            for (int k =i+1 ; k <= m; k++)
                for (int l = 1; l < j; l++)
                {
                    dp[i][j][k][l] = max(max(dp[i - 1][j][k][l - 1], dp[i - 1][j][k - 1][l]), max(dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1])) + g[i][j] + g[k][l];
                }
    cout << dp[m-1][n][m][n-1]<<endl;
    return 0;
}

• 继续优化为三维dp数组
• 将传纸条视为同时从左上开始传两个纸条，
• 用f(k,i,j)表示这一步的横纵坐标之和为x，第一张纸条纵坐标为j，第二张纸条纵坐标为j（因为路径不重合，所以j≠k，不妨令j<k）。
• F[k][i][j]=max({F[k-1][i][j],F[k-1][i-1][j],F[k-1][i][j-1],F[k-1][i-1][j-1]});

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=51;
int F[2*maxn][maxn][maxn];

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> g(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];

    for(int k = 2; k <= m + n; k++) {
        for(int i = 1; i < k && i<=m; i++) {
            for(int j = 1; j < k && j<=m; j++) {
                F[k][i][j]=max({F[k-1][i][j],F[k-1][i-1][j],F[k-1][i][j-1],F[k-1][i-1][j-1]});
                F[k][i][j]+=g[i][k-i]+(i!=j?g[j][k-j]:0);
            }
        }
    }
    cout<<F[m+n][m][m]<<endl;
    return 0;
}

• 滚动数组
• 要注意的就是由于状态都是由更小的j和/或k转移而来，j和k都需要倒序枚举，防止状态在转移之前被修改。

#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

/*
这部分用于在需要时切换标准I/O和文件I/O
当注释掉#include <iostream>时，将使用文件I/O
*/

#ifndef _GLIBCXX_IOSTREAM // 如果未包含<iostream>（即使用文件I/O时）
ifstream cin("0.in");
ofstream cout("0.out");
#endif

int n, m;                 // 网格的行数n和列数m
int f[210][210];          // 动态规划状态数组
int a[210][210];          // 存储网格中每个位置的好感度值

int main()
{
    int i, j, k;

    cin >> n >> m;  // 输入网格行数和列数

    // 读入网格数据
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= m; ++j)
        {
            cin >> a[i][j];
        }
    }

    /*
    动态规划状态初始化：
    第一条路径：起点(1,1) → (1,2)
    第二条路径：起点(1,1) → (2,1)
    初始好感度 = a[1][2] + a[2][1]
    f[1][2] = a[1][2] + a[2][1];

    /*
    动态规划主循环：
    i 表示两条路径当前所在位置的横纵坐标之和（即步数和）
    从4开始：因为起点(1,1)坐标和为2，第一步后坐标和变为3，下一步最小为4
    循环到 n+m-1：最后停在终点(n,m)的前一步（坐标和为n+m-1）
    */
    for (i = 4; i < n + m; ++i)
    {
        /*
        第一层循环：枚举第一条路径所在行号j
        j的范围：从 min(i-2, n) 递减到 1
        - i-2：保证列坐标至少为2（因为坐标和i = 行j + 列，列 = i-j ≥ 1 ⇒ j ≤ i-1，这里取i-2更严格）
        - min(i-2, n)：确保行号不超过网格行数n
        - 倒序枚举：避免覆盖同一轮次中需要使用的状态
        */
        for (j = min(i - 2, n); j >= 1; --j)
        {
            /*
            第二层循环：枚举第二条路径所在行号k
            k的范围：从 min(i-1, n) 递减到 j+1
            - k > j：确保两条路径不相交（第一条路径始终在第二条路径上方）
            - min(i-1, n)：确保行号不超过网格行数n
            - 倒序枚举：保证状态转移的正确性
            */
            for (k = min(i - 1, n); k > j; --k)
            {
                /*
                状态转移：考虑三条路径的移动方向组合
                1. 第一条路径从上方移动而来（j-1 → j）
                2. 两条路径都从上方移动而来（j-1 → j, k-1 → k）
                3. 第二条路径从上方移动而来（k-1 → k）
                */

                // 情况1：第一条路径向下移动
                if (j > 1)
                {
                    f[j][k] = max(f[j][k], f[j - 1][k]);
                }

                // 情况2：两条路径都向下移动
                if (j > 1 && k > 1)
                {
                    f[j][k] = max(f[j][k], f[j - 1][k - 1]);
                }

                // 情况3：第二条路径向下移动（需确保移动后k仍大于j）
                if (k - 1 > j)
                {
                    f[j][k] = max(f[j][k], f[j][k - 1]);
                }

                /*
                添加当前两个位置的好感度：
                - 第一条路径位置：(j, i - j)
                - 第二条路径位置：(k, i - k)
                */
                f[j][k] += a[j][i - j] + a[k][i - k];
            }
        }
    }

    /*
    输出结果：
    - 最终状态：第一条路径在(n-1, m)，第二条路径在(n, m-1)
    - 添加终点(n, m)的好感度（因为两条路径最终都到达终点）
    */
    cout << f[n - 1][n] + a[n][m];

    return 0;
}

解法三：费用流

• 设计费用流，对于每个点流量为 1，费用为那个点的好心程度。

  每个边流量为 1，费用为 0。

  跑最大费用最大流，设 s 为起点，t 为终点。

  因为小渊传完后需要回传，所以 s=t，但是这样 s=t 就直接死循环了。

  并且在费用流中，点，是不能有流量和费用的。

  那咋办，我们化点为边。

  可以这样，把点拆成一个入点和一个出点。

  入点指向出点的边流量和费用就是我们之前讨论的那个点的。

  每个那个点的入点都指向它的入边，出边同样。

  我们 s 设为小渊的出点，t 为小渊的入点，也能避免死循环的问题。

/Dinic 算法  
#include<bits/stdc++.h>
using namespace std;
// #define int long long
int n,m,s,t;
int head[80010],to[240010],nxt[240010],val[240010],cost[240010],tot=1;
void add(int u,int v,int w,int c){
    to[++tot]=v,val[tot]=w,cost[tot]=c;
    nxt[tot]=head[u];
    head[u]=tot;
}
int maxflow,maxcost,dis[80010],now[80010],cnt[80010];
bool vis[80010];
bool spfa(){
    list<int>q;
    memset(dis,-0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    vis[s]=dis[s]=0,now[s]=head[s];
    q.push_back(s);
    while(!q.empty()){
        int u=q.front();
        q.pop_front();
        vis[u]=0;
        for(int i=head[u];i;i=nxt[i]){
            now[to[i]]=head[to[i]];
            if(!val[i]) continue;
            if(dis[to[i]]<dis[u]+cost[i]){
                dis[to[i]]=dis[u]+cost[i];
                cnt[to[i]]=cnt[u]+1;
                if(vis[to[i]]) continue;
                vis[to[i]]=1;
                if(dis[to[i]]<dis[q.empty() ? 0 :q.front()]) q.push_front(to[i]);
                else q.push_back(to[i]);
            }
        }
    }
    memset(vis,0,sizeof vis);
    return dis[t]>dis[0]/2;
}
int dinic(int x,int flow){
    vis[x]=1;
    if(x==t) return flow;
    int rest=flow;
    for(int i=now[x];i && rest;i=nxt[i]){
        now[x]=i;
        if(dis[to[i]]!=dis[x]+cost[i] || !val[i] || vis[to[i]]) continue;
        int v=dinic(to[i],min(rest,val[i]));
        if(!v) dis[to[i]]=dis[0];
        val[i]-=v,val[i^1]+=v,maxcost+=cost[i]*v;
        rest-=v;
    }
    return flow-rest;
}
namespace Input{
    int a[210][210];
    void main() {
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
    }
}
int get(int x,int y,int k){
    return (x-1)*m+y+k*n*m;
}
signed main() {
    ios::sync_with_stdio(0);
    cin>>n>>m;
    s=n*m+1,t=n*m;
    Input::main();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            add(get(i,j,0),get(i,j,1),1,Input::a[i][j]),add(get(i,j,1),get(i,j,0),0,-Input::a[i][j]);
            if(i<n) add(get(i,j,1),get(i+1,j,0),1,0),add(get(i+1,j,0),get(i,j,1),0,0);
            if(j<m) add(get(i,j,1),get(i,j+1,0),1,0),add(get(i,j+1,0),get(i,j,1),0,0);
        }
    }
    int flow=0;
    while(spfa()) while(flow=dinic(s,1e18)) maxflow+=flow;
    cout<<maxcost;
    return 0;
}