题解 | 数位染色

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  这道题本质是问能不能用给出的数（各个数位）凑出所有数的总和
#include <iostream>
#include <bitset>
#include <string>
using namespace std;

bitset<200> dp;

int main(){
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  string s;//----------字符串输入更好处理
  cin >> s;
  int sum = 0;
  size_t size = s.size();
  for (int i = 0; i < size; i++) sum += s[i] - '0';
  if (sum & 1){//----------奇数的一半带有0.5肯定凑不出
    cout << "No";
    return 0;
  }
  dp[0] = 1;
  for (int i = 0; i < size; i++)
    dp |= (dp << (s[i] - '0'));//--------前置题目小M的天平，通过左移来模拟每种情况加上指定的数字
  if (dp[sum / 2]){
    cout << "Yes";
  }
  else cout << "No";
  return 0;
}