题解 | 数位染色

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

string str;
int a[30],len,sum,dp[1000];


int main(){
    cin>>str;
    for(auto x : str){
        a[++len] = x -'0';
        sum += x -'0';
    }

    //奇数一定凑不到
    if(sum&1) return cout<<"No",0;


    //我们只用看看总和的一半能不能被凑到就行了
    dp[0] =  1;

    for(int i = 1;i<=len;i++){
        for(int j = sum/2;j>=a[i];j--){
            dp[j] |= dp[j-a[i]];
        }
    }

    cout<<(dp[sum/2]?"Yes":"No");


    return 0;
}

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344