Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

貌似运作太过庞大了。。。。怎么剪啊。。。

Posted by 4053040 at 2010-02-25 21:44:00 on Problem 3414
In Reply To:为什么我的一执行大数据。超过40就会BUG Posted by:4053040 at 2010-02-25 21:36:35
#include<iostream>
#include<memory>
using namespace std;

struct Que
{
	int value, pre;
};Que que[30000];

int main()
{
	int temp, front, rear;
	int ta, tb;
	int a[40000], b[40000];
	int A, B, C;
	int i, gg;
	int visit[400][400];
	void show(int pre);

	cin >> A >> B >> C;
	if(A % 2 == 0 && B % 2 == 0 % C % 2 != 0) {    //剪枝
		cout << "impossible" << endl;
		return 0;
	} 
	/*if(C > A && C > B) {
		cout << "impossible" << endl;
		return 0;
	} */
	memset(visit, 0, sizeof(visit));
	gg = 0;
	front = rear = 0;
	a[0] = b[0] = 0;
	visit[0][0] = 1;
	que[0].pre = -1;
	que[rear ++].value = 0;
	while(front < rear) {
		temp = front ++;
		if(a[temp] == C || b[temp] == C) {
			gg = 1;
			break;
		}
		for(i = 1; i <= 6; i ++) {
			if(i == 1) {    //1 means full a
				ta = A;
				tb = b[temp];
			}
			if(i == 2) {    // 2 means full b
				ta = a[temp];
				tb = B;
			}
			if(i == 3) {    // 3 means empty a
				ta = 0;
				tb = b[temp];
			}
			if(i == 4) {   // 4 means empty b
				ta = a[temp];
				tb = 0;
			}
			if(i == 5) {   // 5 means a fills b
				if(a[temp] <= B - b[temp]) {  //倒不满
					tb = a[temp] + b[temp];
					ta = 0;
				}
				else {     //溢出
					ta = ta - (B - tb);
					tb = B;
				}
			}
			if(i == 6) {   // 6 means b fills a
				if(b[temp] <= A - a[temp]) {
					ta = a[temp] + b[temp];
					tb = 0;
				}
				else {
					tb = b[temp] - (A - a[temp]);
					ta = A;
				}
			}
			if(visit[ta][tb] == 0) {
				visit[ta][tb] = 1;
				a[rear] = ta;
				b[rear] = tb;
				//que[rear].sum = que[front].sum + 1;
				que[rear].pre = front - 1;
				que[rear ++].value = i;           //储存每次结果。。用于输出
			}
		}
	}
	//cout << front - 1 << endl;
	if(gg == 1) {
		show(front - 1);
	}
	else
		cout << "impossible" << endl;
	
	return 0;
}

int sum = 0;

void show(int pre)
{
	sum ++;
	//cout << pre << endl;
	if(pre == 0) {
		cout << sum - 1 << endl;
		if(que[pre].value == 1)
			cout << "FILL(1)" << endl;
		if(que[pre].value == 2)
			cout << "FILL(2)" << endl;
		if(que[pre].value == 3)
			cout << "DROP(1)" << endl;
		if(que[pre].value == 4)
			cout << "DROP(2)" << endl;
		if(que[pre].value == 5)
			cout << "POUR(1,2)" << endl;
		if(que[pre].value == 6)
			cout << "POUR(2,1)" << endl;
		return ;
	}
	show(que[pre].pre);	
	//cout << que[pre].value << " ";
	if(que[pre].value == 1)
		cout << "FILL(1)" << endl;
	if(que[pre].value == 2)
		cout << "FILL(2)" << endl;
	if(que[pre].value == 3)
		cout << "DROP(1)" << endl;
	if(que[pre].value == 4)
		cout << "DROP(2)" << endl;
	if(que[pre].value == 5)
		cout << "POUR(1,2)" << endl;
	if(que[pre].value == 6)
		cout << "POUR(2,1)" << endl;
	return ;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator