# 🌱 Lời giải Mely Educational Contest 04 bài E : Tình đoàn kết

>[color=pink] Nếu bạn cảm thấy Edit này chất lượng tiếc gì một upvote và giới thiệu team với mọi người nhé :heart:

###### 📋 Content:
[TOC]
____
## Nhận xét :label:
:question: Ta có thể tiếp cận bài này bằng công thức quy hoạch động như sau :
>[color=green]
>- Gọi $DP[i][j][k]$ là liệu chênh lệch tổng số kẹo giữa 2 bạn đến ô ***(i,j)*** có là ***k*** được hay không ? (để dễ xử lí ta gán *$DP[i][j][k]$ = 1* là "được", ngược lại ta gán *$DP[i][j][k]$ = 0*)
>- Nếu ô ***(i,j)*** có độ chênh lệch là ***k***, thì đến ô ***(i+1,j)*** chênh lệnh chỉ có thể bằng ***k+|a[i][j] − b[i+1][j]|*** hoặc ***|k-|a[i][j] − b[i+1][j]||***.
>- Từ nhận xét trên, ta có thể viết công thức chuyển trạng thái cho ô ***(i+1,j)*** ngắn gọn với phép toán ***OR*** như sau:
>- $DP[i+1][j][nxt]$ |= $DP[i][j][k]$ (với **k** là chênh lệch ở ô ***(i,j)*** hiện tại,***nxt*** là chênh lệch ở ô ***(i+1,j)***)
>- Công thức cho ô ***(i,j+1)*** hoàn toàn tương tự !

## Code mẫu :bulb:
> **Time:** $O(M*N*(M+N)*W)$ (với ***W*** là chênh lệch tối đa của 2 đống kẹo trong 1 ô)
> **Space:** $O(M*N*(M+N)*W)$
> **Algo:** Dynamic programing.
> [color=lightgreen]
:::success
:::spoiler code mẫu

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
//#define int long long
using namespace std;
using ll = long long;
const int maxN = 2e5 + 5;
const int N = 2e6;
const int mod = 1e9 + 7;

int m,n;
int a[81][81];
int b[81][81];
int c[81][81];
bool dp[81][81][80*160];

void Solve()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin >> b[i][j];
            c[i][j] = abs(a[i][j]-b[i][j]);
        }
    }

    dp[1][1][c[1][1]] = 1;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 0; k <= 80 * (i+j-1); k++)
            {
                if(i == m && j == n)
                {
                    if(dp[i][j][k])
                    {
                        cout << k;
                        return;
                    }
                    else continue;
                }
                if(i+1 <= m)
                {
                    dp[i+1][j][k+c[i+1][j]] |= dp[i][j][k];
                    dp[i+1][j][abs(k-c[i+1][j])] |= dp[i][j][k];
                }
                if(j+1 <= n)
                {
                    dp[i][j+1][k+c[i][j+1]] |= dp[i][j][k];
                    dp[i][j+1][abs(k-c[i][j+1])] |= dp[i][j][k];
                }
            }
        }
    }


}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //Prepare();
    int tt;
    //cin >> tt;
    tt = 1;
    while(tt--)
    {
        Solve();
    }
}

:::success