UVA-10400 Game Show Math(遡及)


n個の数字を与えて、1つの表現で計算することができるかどうかを聞いて、目標値.加算減算の優先度は同じです.
解析:遡及+状態再判断では、1次元目に位置を記録し、2次元記録sumが現れたかどうかの2次元vis配列を開くことができます.次にsum==tarの場合、現在の記号をans配列に保存します.
注意-32000<=sum<=32000
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 110;
const int MAX = 32000;

int tar;

int num[N];
int vis[N][100000];
char path[N],ans[N];
bool flag;
int n;

bool judge(int sum,int pos) {
	if(sum >= -MAX && sum <= MAX && !vis[pos][sum+MAX]) {
		return true;
	}
	return false;
}

void dfs(int sum,int pos) {
	if(pos == n) {
		if(sum == tar && !flag) {
			for(int i = 0; i <= n; i++) {
				ans[i] = path[i];
			}
			flag = true;
		}
		return;
	}
	if(!flag) { //+
		if(judge(sum+num[pos],pos)) {
			vis[pos][sum+num[pos]+MAX] = true;
			path[pos] = '+';
			dfs(sum+num[pos],pos+1);
		}
	}
	if(!flag) { //-
		if(judge(sum-num[pos],pos)) {
			vis[pos][sum-num[pos]+MAX] = true;
			path[pos] = '-';
			dfs(sum-num[pos],pos+1);
		}
	}
	if(!flag) { //*
		if(judge(sum*num[pos],pos)) {
			vis[pos][sum*num[pos]+MAX] = true;
			path[pos] = '*';
			dfs(sum*num[pos],pos+1);
		}
	}
	if(!flag) { // %
		if(sum % num[pos] == 0) {
			if(judge(sum/num[pos],pos)) {
				vis[pos][sum/num[pos]+MAX] = true;
				path[pos] = '/';
				dfs(sum/num[pos],pos+1);
			}
		}
	}
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
		for(int i = 0; i < n; i++) {
			scanf("%d",&num[i]);
		}
		scanf("%d",&tar);
		memset(vis,0,sizeof(vis));
		memset(path,'=',sizeof(path));
		vis[0][num[0]+MAX] = true;
		flag = false;
		dfs(num[0],1);
		if(flag) {
			for(int i = 0; i < n; i++) {
				printf("%d%c",num[i],ans[i+1]);
			}
			printf("%d
",tar); }else { printf("NO EXPRESSION
"); } } return 0; }