题解 | 数位染色

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 19;
bool dp[MAXN][MAXN * 9 + 1];//根据题意开个18层，因为我下标从1开始就定19了，每位数都有9种可能

int main() {
    string s;cin >> s;
    
    int sum = 0;
    for (int i = 0; i < s.size(); i++) sum += (s[i] - '0');

    if (sum % 2) {//和为计数染不了色
        cout << "No";
        return 0;
    }
    
    int half = sum / 2;
    dp[0][0] = 1; //初始化第一层，只有0种颜色
    

    //bool dp[i][j]表示前i位，颜色种类j是否可达
    for (int i = 1; i <= s.size(); ++i) 
    {
        // 将当前字符转换为对应的数字
        int tmp = s[i-1] - '0';

        //枚举颜色种类j
        for (int j = 1; j <= half; ++j) 
        {
            //先继承上一层的状态(不选)
            dp[i][j] = dp[i - 1][j];
            //看看能否从dp[i - 1][j - tmp]转移过来(选)
            if(j >= tmp)dp[i][j] |= dp[i - 1][j - tmp];
        }
    }
    
    if (dp[s.size()][half]) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    
    return 0;
}