#define INFINIT 20

#include <iostream>
using namespace std;

int stack[12],stack_ptr;
int iarray[10][2],isum_array,isum_cmd,imin_cmd;
char cmd[12],mincmd[12];
char cmdbase[8]={'A','S','M','D','C'};

int evaluate(void)
//check for feasibility
{
	int i,j,state(1);

	for(i=0;i<isum_array;++i)
	{
		stack[stack_ptr=0]=iarray[i][0];
		for(j=0;j<isum_cmd;++j)
		{
			switch(cmd[j])
			{
				case 'A':
				{
					if(0==stack_ptr)
						return -1;
					--stack_ptr;
					stack[stack_ptr]+=stack[stack_ptr+1];
				}
				break;

				case 'S':
				{
					if(0==stack_ptr)
						return -1;
					--stack_ptr;
					stack[stack_ptr]-=stack[stack_ptr+1];
				}
				break;

				case 'M':
				{
					if(0==stack_ptr)
						return -1;
					--stack_ptr;
					stack[stack_ptr]*=stack[stack_ptr+1];
				}
				break;

				case 'D':
				{
					if(0==stack_ptr||0==stack[stack_ptr])
						return -1;
					--stack_ptr;
					stack[stack_ptr]/=stack[stack_ptr+1];
				}
				break;

				case 'C':
				{
					stack[stack_ptr+1]=stack[stack_ptr];
					++stack_ptr;
				}
			}
			if(stack[stack_ptr]>30000||stack[stack_ptr]<-30000)
				return -1;
		}
		if(stack[stack_ptr]!=iarray[i][1])
			state=0;
	}
	return state;
}

void dfs(int index)
//isum_cmd is a global var for evaluate()
{
	int i,j,state;

	isum_cmd=index;
	if(index>10)
		return;
	if(isum_cmd>=imin_cmd)
		return;

	state=evaluate();
	if(1==state)
	{
		if(isum_cmd<imin_cmd)
		{
			imin_cmd=isum_cmd;
			for(i=0;i<isum_cmd;++i)
				mincmd[i]=cmd[i];
		}
		return;
	}
	else if(-1==state)
		return;

	isum_cmd=index+1;
	if(isum_cmd>=imin_cmd||isum_cmd>10)
		return;

	for(i=0;i<5;++i)
	{
		cmd[index]=cmdbase[i];
		dfs(index+1);
	}
}

int main(void)
{
	int round(0),i;

	while(++round)
	{
		cin>>isum_array;
		if(0==isum_array)break;
		if(round>1)
			cout<<endl;
		cout<<"Program "<<round<<endl;

		for(i=0;i<isum_array;++i)
			cin>>iarray[i][0];
		for(i=0;i<isum_array;++i)
			cin>>iarray[i][1];
		isum_cmd=0;
		imin_cmd=INFINIT;
		dfs(0);
		if(imin_cmd<INFINIT)
		{
			if(0==imin_cmd)
				cout<<"Empty sequence";
			else
				for(i=0;i<imin_cmd;++i)
				{
					if(i)
						cout<<" ";
					switch(mincmd[i])
					{
						case 'A':
						{
							cout<<"ADD";
							break;
						}

						case 'S':
						{
							cout<<"SUB";
							break;
						}

						case 'M':
						{
							cout<<"MUL";
							break;
						}

						case 'D':
						{
							cout<<"DIV";
							break;
						}

						case 'C':
							cout<<"DUP";
					}
				}
		}
		else
			cout<<"Impossible";

		cout<<endl;
	}

	return 0;
}

• 终于过了 原来是没有看到 如果有两条一上的符合条件 则选择字典序靠前的 ～～～～晕哦 (0) Allan 2006-09-18 19:47:21
  • Re:哎,还有这事 (0) 407811696 2011-01-17 12:55:10