uva10344 一次AC

題意是給定5個正整數，通過加，減，乘法運算計算23，計算順序有一定的格式要求：

For this problem we will only consider arithmetic expressions of the following from:

where 
        
  
             
: {1,2,3,4,5} -> {1,2,3,4,5} is a bijective function      

and 
        
  
             
 {+,-,*} (1<=i<=4)      

我采用回溯法，因為隻有五個數，運算符和隻有三個，是以複雜度并不高，也是卡着時間限AC的      

#include<iostream>

using namespace std;

int data[5];
bool ok,vis[5];

void dfs(int cur,int result)
{
	int i;
	if (cur==5)
	{
		if (result==23) ok=1;
	}
	else 
	{
		for (i=0;i<5;i++)
		{
			if (!vis[i])
			{
				vis[i]=1;
				dfs(cur+1,result+data[i]);
				dfs(cur+1,result-data[i]);
				dfs(cur+1,result*data[i]);
				vis[i]=0;
			}
		}
	}
}
int main()
{
	int a;
	while (cin>>a&&a)
	{
		data[0]=a;
		for (int i=1;i<=4;i++)
		{
			cin>>data[i];
		}
		ok=0;
		for (int i=0;i<5;i++)
		{
			vis[i]=1;
			dfs(1,data[i]);
			vis[i]=0;
			if (ok) break;
		}
		if (ok) cout<<"Possible"<<endl;
		else cout<<"Impossible"<<endl;
	}
	return 0;
}