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