E – Balanced Path

题目描述：

n * m的矩阵，每个矩阵上有两个值，一个a,一个b，这个点的价值是a-b或者是b-a，问从(1, 1)走到(n, m)的路径中能得到的总价值的绝对值最小是多少

思路：

设dp[i][j][k]表示从(1, 1)走到(i, j)后的总价值是否能为k,如果为1，则能为k，否则则不能

就类似于最简单的方格取数的dp一样去转移

由于权值存在负数，而负数下标是不能访问的，但是，从定义出发，我们从(1, 1)走到(i, j)的路径的总价值为-k的情况，是一定存在一条同样的路径，取每个点的相反数的到总价值为k，所以我们套一个绝对值就行

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

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
bool dp[81][81][6401];
int ar[81][81];
int br[81][81];

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> ar[i][j];
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> br[i][j];
        }
    }
    dp[0][1][0] = dp[1][0][0] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            int d = ar[i][j] - br[i][j];
            for(int k = 0; k <= 6400; ++k){
                if(k + d <= 6400)dp[i][j][abs(k + d)] |= dp[i - 1][j][k] | dp[i][j - 1][k];
                if(k - d <= 6400)dp[i][j][abs(k - d)] |= dp[i - 1][j][k] | dp[i][j - 1][k];
            }
        }
    }
    for(int i = 0; i <= 6400; ++i){
        if(dp[n][m][i]){
            cout << i << endl;
            return;
        }
    }
}


int main(){
    io;
    work();
    return 0;
}