toj_2948_zwd.cpp

来自「Tianjin University Online Judge 的80多道题目 」· C++ 代码 · 共 72 行

 #include <stdio.h>
 #include<cstdlib>
 #include<cstring>
#define MAXNUM 30
int n;
double p[ MAXNUM ][ MAXNUM ],max=0;
double pM[ MAXNUM ] , pMul[ MAXNUM ];

bool f[ MAXNUM ];

void dfs(int num,double temp)
{
    
	if(temp<max)
		return;
	int i;
        double remainMax;
        
	if(num==n)
	{
		if(temp>max)
			max=temp;
	}
	else
	{
            remainMax = 1;
            for( i = 0; i < n; i++ )
                if( !f[ i ] )
                    remainMax *= pM[ i ];
            if( temp * remainMax < max )
                return;
		for(i=0;i<n;i++)
		{
			if(!f[i])
			{
				f[i]=1;
				dfs(num+1,temp*p[num][i]);
				f[i]=0;
			}
		}
	}
}

int main()
{
    int t,i,j;
//    freopen( "toj_2948.in" , "r" , stdin );
//    freopen( "toj_2948.out" , "w" , stdout );
//    while( scanf("%d",&n) && n  ){
    scanf( "%d" , &n );
    memset( f , 0 , sizeof( f ) );
    memset( pM , 0 , sizeof( pM ) );
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&t);
            p[i][j]=t/100.0;
        }
    for( i = 0; i < n; i++ )
        for( j = 0; j < n; j ++ )
            if( pM[ i ] < p[ j ][ i ] )
            pM[ i ] = p[ j ][ i ];
//     pMul[ n ] = 1;
//     for( i = n - 1; i >= 0; i-- )
//         pMul[ i ]  = pMul[ i + 1 ] * pMax[ i ];
    max = -1;
    dfs(0,1);
    printf("%lf\n",max*100.0);
//    }
    return 0;
}