多米诺骨牌

二维数组

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005], b[1005];
const int BASE = 5 * 1000 + 5;
// 前 i 项，差为 j 时最少反转次数（+Base）
int dp[1005][11234];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int suma = 0;
    int sumb = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        suma += a[i];
        sumb += b[i];
    }
    memset(dp, -1, sizeof(dp));
    dp[0][suma - sumb + BASE] = 0;
    for (int i = 1; i <= n; i++)
    {
        int now = (b[i] - a[i]) - (a[i] - b[i]);
        for (int j = -5000; j <= 5000; j++)
        {
            dp[i][j + BASE] = dp[i - 1][j + BASE];
            if (dp[i - 1][j + BASE - now] != -1)
            {
                if (dp[i][j + BASE] == -1)
                    dp[i][j + BASE] = dp[i - 1][j + BASE - now] + 1;
                else
                    dp[i][j + BASE] = min(dp[i][j + BASE], dp[i - 1][j + BASE - now] + 1);
            }
        }
    }
    for (int i = 0; i <= 5000; i++)
    {
        if (dp[n][i + BASE] == -1 && dp[n][-i + BASE] == -1)
            continue;
        if (dp[n][i + BASE] == -1)
        {
            cout << dp[n][-i + BASE];
            return 0;
        }
        if (dp[n][-i + BASE] == -1)
        {
            cout << dp[n][i + BASE];
            return 0;
        }
        cout << min(dp[n][-i + BASE], dp[n][i + BASE]);
        return 0;
    }
    return 0;
}

一维数组

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005], b[1005];
const int BASE = 5 * 1000 + 5;
//当差为i时最少反转次数（+Base）
int dp[11234];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int suma = 0;
    int sumb = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        suma += a[i];
        sumb += b[i];
    }
    memset(dp, -1, sizeof(dp));
    dp[suma - sumb + BASE] = 0;
    for (int i = 1; i <= n; i++)
    {
        int now = (b[i] - a[i]) - (a[i] - b[i]);
        if (now > 0)
        {
            for (int j = 5000; j >= -5000; j--)
                if (dp[j + BASE - now] != -1)
                {
                    if (dp[j + BASE] == -1)
                        dp[j + BASE] = dp[j + BASE - now] + 1;
                    else
                        dp[j + BASE] = min(dp[j + BASE], dp[j + BASE - now] + 1);
                }
        }
        else
        {
            for (int j = -5000; j <= 5000; j++)
                if (dp[j + BASE - now] != -1)
                {
                    if (dp[j + BASE] == -1)
                        dp[j + BASE] = dp[j + BASE - now] + 1;
                    else
                        dp[j + BASE] = min(dp[j + BASE], dp[j + BASE - now] + 1);
                }
        }
    }
    for (int i = 0; i <= 5000; i++)
    {
        if (dp[i + BASE] == -1 && dp[-i + BASE] == -1)
            continue;
        if (dp[i + BASE] == -1)
        {
            cout << dp[-i + BASE];
            return 0;
        }
        if (dp[-i + BASE] == -1)
        {
            cout << dp[i + BASE];
            return 0;
        }
        cout << min(dp[-i + BASE], dp[i + BASE]) << endl;
        return 0;
    }
    return 0;
}