Coin Toss

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31329#problem/G

使用二维数组f[ i ] [ j  ] 表示前i 位中有j个连续的硬币。

当第i个硬币等于j+1时,那么当j 个硬币恰在第i个硬币前面时,那么则有j + 1个,所以f[i ][ j ] 需要减去1个;当i >j + 1时,那么在第j + 1 个之前的数必须是T;所以需要减去f[ i - ( j +1 ) - 1 );

import java.math.BigInteger ;
import java.util.Scanner; public class Main
{
public static void main( String[ ] args )
{
Scanner cin = new Scanner( System.in ) ;
BigInteger[][] f = new BigInteger[ 105 ][ 105 ] ;
for( int i = 0 ; i <= 100 ; ++i )
{
f[ 0 ][ i ] = new BigInteger( "1" ) ;
}
f[ 1 ][ 0 ] = new BigInteger( "1" ) ;
for( int i = 1 ; i <= 100 ; ++i )
{
f[ 1 ][ i ] = new BigInteger( "2" ) ;
}
for( int i = 2 ; i <= 100 ; ++i )
{
for( int j = 0 ; j <= 100 ; ++j )
{
f[ i ][ j ] = f[ i - 1 ][ j ].multiply( BigInteger.valueOf( 2 ) ) ;
if( i == j + 1 )
{
f[ i ][ j ] = f[ i ][ j ].add( BigInteger.valueOf( -1 ) ) ;
}
else if( i > j + 1 )
{
f[ i ][ j ] = f[ i ][ j ].add( f[ i - j - 2 ][ j ].negate() ) ;
}
}
}
while( cin.hasNext())
{
int n = cin.nextInt();
int k = cin.nextInt();
System.out.println( f[ n ][ n ].add( f[ n ][ k - 1 ].negate()) ) ;
}
}
}
上一篇:azure上连续部署web


下一篇:ZOJ1204——Additive equations(DFS)