3174577_ac_921ms_4872k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main
{

	public static boolean meet(int i,int j,int n)
	{
		int k, p, l;

		l = 1<<n;
		for(k = 1; ; k+=l)
		{
			if(i >= k && i < k+l)
			{
				break;
			}
		}
		if(j < k || j >= k+l)
			return false;
		l = l>>1;
		for(p = 1; ; p+=l)
		{
			if(i >= p && i < p+l)
			{
				break;
			}
		}
		return !(j >= p && j < p+l);
	}

	public static void main(String [] args)
	{
		Scanner cin = new Scanner (System.in);
		double [][] p = new double [129][129];
		int n;

		while(true)
		{
			n = cin.nextInt();
			if(n==-1)
				break;
			for(int i = 1; i <= 1<<n; i++)
			{
				for(int j = 1; j <= 1<<n; j++)
				{
					p[i][j] = cin.nextDouble();
				}
			}
			double [][] ans = new double [n+1][1<<n+1];
			Arrays.fill(ans[0],1);
			for(int i = 1; i <= n; i++)
			{
				for(int j = 1; j <= 1<<n; j++)
				{
					ans[i][j] = 0;
					for(int k = 1; k <= 1<<n; k++)
					{
						if(meet(j,k,i))
						{
							ans[i][j] += ans[i-1][j]*ans[i-1][k]*p[j][k];
						}
					}
				}
			}
			int winner = 0;
			double max = 0;
			for(int i = 1; i <= 1<<n; i++)
			{
				if(ans[n][i] > max)
				{
					max = ans[n][i];
					winner = i;
				}
			}
			System.out.println(winner);
		}
	}
}