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 bighand at 2009-05-26 11:53:11 on Problem 1179
#include <iostream>
using namespace std;
//表示最小值的
long mi[52][52];
//表示最大值的
long ma[52][52];
int n;
char edge[52];
int vec[52];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> edge[i-1];
		cin >> vec[i];
	}
	edge[n]=edge[0];
	long temp;
	for (int len = 0; len < n; len++) {
		for (int i = 1; i <= n; i++) {
			int j=(i+len-1)%n+1;
			if (len == 0) {
				mi[i][j] = ma[i][j] = vec[i];
			} else {
				ma[i][j]=-999999;
				mi[i][j]=999999;
				int counter=0;
				while(true){
					if(counter==len) break;
					int k=(i+counter-1)%n+1;
					int k1=k%n+1;
					counter++;
					if (edge[k] == 't') {
						int temp = ma[i][k] + ma[k1][j];
						if (temp > ma[i][j])
							ma[i][j] = temp;
						temp= mi[i][k] + mi[k1][j];
						if(temp<mi[i][j])
							mi[i][j] = temp;
					} else {
						temp = ma[i][k] * ma[k1][j];
						if (temp > ma[i][j])
						   ma[i][j] = temp;
							if(temp<mi[i][j])
						  mi[i][j] = temp;
						temp = ma[i][k] * mi[k1][j];
						if (temp > ma[i][j])
							ma[i][j] = temp;
						 if(temp<mi[i][j])
							mi[i][j] = temp;
						temp = mi[i][k] * ma[k1][j];
						if (temp > ma[i][j])
							ma[i][j] = temp;
						 if(temp<mi[i][j])
							mi[i][j] = temp;
						temp = mi[i][k] * mi[k1][j];
						if (temp > ma[i][j])
							ma[i][j] = temp;
						 if(temp<mi[i][j])
							mi[i][j] = temp;
					}
				}
			}
		}
	}
	long max=0;
	int p;
	for(int i=1;i<=n;i++){
		p=(i+n-2)%n+1;
		if(ma[i][p]>max) max=ma[i][p];
	}
	cout<<max<<endl;
	bool head=1;
	for(int i=1;i<=n;i++){
		p=(i+n-2)%n+1;
		if(ma[i][p]==max) {
			if(head) {
				cout<<i;
				head=0;
			}else{
				cout<<" "<<i;
			}

		}
	}
	cout<<endl;
	return 0;
}


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