UVa-11832 : Account Book

問題概要

長さN(<40)の数列A(abs(A[i])<=1000=:T)がある。sum sign[i]*A[i] = Fとなるような符号の付け方に関して、一意に定まるものは正か負かを、定まらないものはその旨出力する。どうやってもできないときはその旨出力する。

解法

今いくつの数字を持っているかをキーにしてDP。詳細はコード参照。
多分Tが大きくても半分全列挙でO(2^(N/2)*N)くらいで解ける…はず。

acceptされたコード

計算量O(N^2*T)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = 40;
const int MAX_T = 1000;

int N, F;
int as[MAX_N];
int64 plus[MAX_N+1][2*MAX_N*MAX_T + 1];
int64 minus[MAX_N+1][2*MAX_N*MAX_T + 1];

bool init(){
	memset(plus, 0, sizeof(plus));
	memset(minus, 0, sizeof(minus));

	scanf("%d%d", &N, &F);
	for(int i=0; i<N; i++){
		scanf("%d", as + i);
	}

	return !(N==0 && F==0);
}

void solve(){
	F += MAX_N*MAX_T;
	int mini = MAX_N*MAX_T, maxi = MAX_N*MAX_T;

	for(int i=0; i<N; i++){
		for(int v=mini; v<=maxi; v++)if(plus[i][v]>0 || minus[i][v]>0 || (i==0 && v==MAX_N*MAX_T)){
			plus[i+1][v+as[i]] |= plus[i][v] | (1LL<<i);
			minus[i+1][v+as[i]] |= minus[i][v];
			plus[i+1][v-as[i]] |= plus[i][v];
			minus[i+1][v-as[i]] |= minus[i][v] | (1LL<<i);
			maxi = max(maxi, v + as[i]);
			mini = min(mini, v - as[i]);
		}
	}

	if(plus[N][F] == 0 && minus[N][F] == 0){
		puts("*");
	}
	else{
		for(int i=0; i<N; i++){
			if( (plus[N][F]>>i)&1 ){
				if( (minus[N][F]>>i)&1 ){
					putchar('?');
				}
				else{
					putchar('+');
				}
			}
			else{
				putchar('-');
			}
		}
		puts("");
	}
}

int main(){
	while(init()){
		solve();
	}

	return 0;
}