[UVa] 10400 - Game Show Math

題意:
(from luckycat)


解法:
用 DFS backtrack 所有可能，但是要搭配剪枝篩掉一些情況。
1. 所有計算出來的數字都要在他規定的範圍內 -32000 ~ 32000
2. 除法只能在能整除時使用
3. 用 vis[num][value] 來記錄當前情況是否已檢查過

注意:

程式碼:

	/**
	* Tittle: 10400 - Game Show Math
	* Author: Cheng-Shih, Wong
	* Date: 2015/08/13
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define F first
	#define S second
	#define PB push_back
	#define INF 32000
	#define N 105
	// declarations
	int t;
	int n, target;
	bool vis[N][2*INF+5];
	vector<int> num;
	vector<char> op;
	// functions
	void output()
	{
	cout << num[0];
	FOR( i, 1, op.size() )
	printf( "%c%d", op[i-1], num[i] );
	printf( "=%d\n", target );
	}
	bool dfs( int idx, int res )
	{
	if( !vis[idx][INF+res] ) vis[idx][INF+res] = true;
	else return false;
	if( idx == n ) {
	return res == target;
	}
	// +
	if( res+num[idx] <= INF ) {
	op.PB( '+' );
	if( dfs(idx+1, res+num[idx]) )
	return true;
	op.pop_back();
	}
	// -
	if( res-num[idx] >= -INF ) {
	op.PB( '-' );
	if( dfs(idx+1, res-num[idx]) )
	return true;
	op.pop_back();
	}
	// *
	if( -INF <= res*num[idx] && res*num[idx] <= INF ) {
	op.PB( '*' );
	if( dfs(idx+1, res*num[idx]) )
	return true;
	op.pop_back();
	}
	// /
	if( res%num[idx] == 0 ) {
	op.PB( '/' );
	if( dfs(idx+1, res/num[idx]) )
	return true;
	op.pop_back();
	}
	return false;
	}
	// main function
	int main( void )
	{
	int v;
	bool valid;
	// input
	cin >> t;
	while( t-- ) {
	cin >> n;
	num.clear();
	FOR( i, 1, n ) {
	cin >> v;
	num.PB( v );
	}
	cin >> target;
	op.clear();
	clr( vis, false );
	valid = dfs( 1, num[0] );
	// output
	if( !valid ) puts("NO EXPRESSION");
	else output();
	}
	return 0;
	}

view raw 10400 - Game Show Math.cpp hosted with ❤ by GitHub