题解 | #数位染色#

类似背包问题，sum为所有位数之和，k=sum/2，将k看成背包容量，将原背包问题中的求最值问题看作存在性问题；dp[j]为背包剩余量。第i位数有选或不选两种情况。

dp[j]=(dp[j+m[i]]||dp[j]);

#include<iostream>
using namespace std;

int main(){
    long long x;
    bool dp[100]={0};
    int m[20]={0};
    int sum=0;
    int n=0;
    cin>>x;
    while(x!=0){
        ++n;
        m[n]=x%10;
        sum+=x%10;
        x/=10;
    }
    if(sum%2==0){
        int k=sum/2;
        dp[k]=1;
        for(int i=0;i<n;++i){
            for(int j=0;j+m[i]<=k;++j){
                dp[j]=dp[j+m[i]]||dp[j];
            }
        }
        if(dp[0]==1)
            cout<<"Yes";
        else
            cout<<"No";
    }
    else
        cout<<"No";
    return 0;
}