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

水题一个!308K 0ms 数据弱,不需要过多纠结考慮精度問題

Posted by KatrineYang at 2016-08-31 12:22:29 on Problem 1238
#include <iostream>
#include <stdio.h>
using namespace std;

int N;

double h[35][35];
double dp[35][35][35];
int trc[35][35][35];

int main() {
	while(scanf("%d", &N) > 0){
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				if(i == j) h[i][j] = 0.0;
				else scanf("%lf", &h[i][j]);
			}
		}
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				//if(i == j) continue;
				dp[1][i][j] = h[i][j];
				trc[1][i][j] = i;
			}
		}
		int startP = -1, cs = 2333;
		for(int k = 2; k <= N; k++){
			for(int i = 1; i <= N; i++){
				for(int j = 1; j <= N; j++){
					double mx = 0.0;
					int arg = -1;
					for(int j_ = 1; j_ <= N; j_++){
						if(j_ == j) continue;
						double temp = dp[k-1][i][j_] * h[j_][j];
						if(temp > mx){
							mx = temp;
							arg = j_;
						}
					}
					dp[k][i][j] = mx;
					trc[k][i][j] = arg;
					if(i == j && mx > 1.01){
						startP = i;
						cs = k;
						goto done;
					}
				}
			}
		}
		done:
		if(startP == -1){
			printf("no arbitrage sequence exists\n");
			continue;
		}
		int seq[35];
		seq[cs] = startP;
		int pos = cs;
		int cur = trc[cs][startP][startP];
		while(pos > 0){
			pos--;
			seq[pos] = cur;
			cur = trc[pos][startP][cur];
		}
		for(int i = 0; i <= cs; i++){
			printf(" %d", seq[i]);
		}
		printf("\n");
	}
	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