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; }