UVa 11832 : Account Book

UVa演習 2014/6/10 (火) 問４

問題リンク : http://uva.onlinejudge.org/external/118/11832.html

問題概要：
N個の正の整数が与えられる
これらに任意の符号を付け、その総和をFにしたい
各整数の符号を決定し、正でも負でも良いなら'?',正なら'+',負なら'-'と出力せよ
そもそもFにできない場合は一行に'*'と出力せよ

解法：
メモ化再帰
memo[現在の値][N個の整数のi番まできた] := i番以降をうまく選んだ時に総和をFにできるか
もうひとつ配列を用意し、i番目の整数を正として使ってFにできるか、負として使ってFにできるかを記録する

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int LIMIT = 16000*2 + 400010, coef = 100000;
short buf[LIMIT][50];
bool ok[50][2];
int N,F,T[50],neg;

bool dfs(int remain,int cur){

  if( cur >= N ) return remain == 0;
  if( buf[remain+coef][cur] >= 0 ) return buf[remain+coef][cur];
  bool ret = false;

  if( dfs(remain+T[cur],cur+1) ) {
    ok[cur][1] = true;
    ret = true;
  }

  if( dfs(remain-T[cur],cur+1) ) {
    ok[cur][0] = true;
    ret = true;
  }
  return buf[remain+coef][cur] = ret;
}

int main(){
  while( cin >> N >> F, N|F ){
    rep(i,LIMIT) rep(j,50) buf[i][j] = -1;
    rep(i,50) rep(j,2) ok[i][j] = false;
    rep(i,N) cin >> T[i];

    if(!dfs(F,0)){
      puts("*");
    } else {
      rep(i,N){
        if( ok[i][0] && ok[i][1] ) printf("%c",'?');
        else if( ok[i][0] )        printf("%c",'+');
        else if( ok[i][1] )        printf("%c",'-');
      } puts("");
    }

  }
  return 0;
}