UVa1238

UVa1238

DPする。
dp[どこまで見た][閉じていない開き括弧の数][これまでの和]
+ に括弧を付けても意味がないので、- のところに括弧を付ける。
- ( ... - ( ... - ( ) ... ) ... - ( ) ... ) みたいになるとして、
閉じられていない括弧の数が偶数か奇数かどうかで、今見ている数の符号が反転するかどうか分かる。

#include <algorithm>
#include <iostream>
#include <sstream>
#include <set>

using namespace std;

const int N = 35;
const int M = (3000 + 1) * 2;
int size;
int num[N];
char op[N];
bool dp[N][N][M];

int main(int argc, char *argv[])
{
  for (string s; getline(cin, s); ) {

    istringstream iss(s);
    for (iss >> num[size = 0]; iss >> op[size++]; iss >> num[size]) ;
    op[size - 1] = '=';

    fill(&dp[0][0][0], &dp[N - 1][N - 1][M], false);
    dp[1][0][num[0] + 3000] = true;

    for (int i = 1; i < (int)size; ++i) {
      for (int j = 0; j < (int)size; ++j) {
        for (int k = 0; k < (int)M; ++k) {
          if (!dp[i][j][k]) continue;
          int l = k + ((j + (op[i - 1] == '-')) % 2 ? -1 : +1) * num[i];
          dp[i + 1][j][l] = true;
          if (j) {
            dp[i + 1][j - 1][l] = true;
          }
          if (op[i - 1] == '-') {
            int l = k + ((j + 1) % 2 ? -1 : +1) * num[i];
            dp[i + 1][j + 1][l] = true;
          }
        }
      }
    }

    set<int> res;
    for (int i = 0; i < (int)N; ++i) {
      for (int j = 0; j < (int)M; ++j) {
        if (dp[size][i][j]) res.insert(j - 3000);
      }
    }
    cout << res.size() << endl;
  }
  return 0;
}