题解 | #数位染色#

#include <iostream>
#include <cstring>
using namespace std;

int main() 
{
    char arr[20] = {0};
    int arr1[20] = {0};
    int sum = 0;
    cin >> arr;
    int len = strlen(arr);
    for (int i = 0; i < len; i++)
    {
        arr1[i] = arr[i] - '0';
    }
    for (int i = 0; i < len; i++)
    {
        sum += arr1[i];
    }
    int p[sum/2 + 1];
    for (int i = 0; i < sum/2 + 1; i++)
    {
        p[i] = 0;
    }
    if (sum % 2 == 0)
    {
        for (int i = 0; i < len; i++)
        {
            for (int j = sum/2; j >= arr1[i]; j--)
            {
                p[j] = (p[j-arr1[i]] + arr1[i]) > p[j-1] ? (p[j-arr1[i]] + arr1[i]) : p[j-1];
                if (p[j] == sum/2)
                {
                    cout << "Yes";
                    return 0;
                }
            }

        }

    }
    cout << "No";
    

    return 0;
}
// 64 位输出请用 printf("%lld")