首页 > 专题系列 > Java解POJ > POJ 2537 Tight words [解题报告] Java
2013
11-11

POJ 2537 Tight words [解题报告] Java

Tight words

问题描述 :

Given is an alphabet {0, 1, … , k}, 0 <= k <= 9 . We say that a word of length n over this alphabet is tight if any two neighbour digits in the word do not differ by more than 1.

输入:

Input is a sequence of lines, each line contains two integer numbers k and n, 1 <= n <= 100.

输出:

For each line of input, output the percentage of tight words of length n over the alphabet {0, 1, … , k} with 5 fractional digits.

样例输入:

4 1
2 5
3 5
8 7

样例输出:

100.00000
40.74074
17.38281
0.10130

解题代码:

//* @author:
import java.util.*;
public class Main {
 
static public void main( String [] str ){
   Scanner sc = new Scanner(System.in);
   while( sc.hasNext())
   {
     double s=1,answer;
     int k=sc.nextInt();
     int n=sc.nextInt();
     double ans[][]=new double[n][k+1];
     for( int i=0; i< n; i++ )
	s *= (k+1);

     for(int  j=0; j<=k; j++ )
	ans[0][j] = 1/s;

     for(int  i=1; i< n; i++ )
	for(int j=0; j<=k; j++ )
	{
	   ans[i][j] = ans[i-1][j];
	   if( j!=0) ans[i][j] += ans[i-1][j-1];
	   if( j< k ) ans[i][j] += ans[i-1][j+1];
	}
		
     answer = 0;
     for( int j=0; j<=k; j++ )
	answer += ans[n-1][j];
     System.out.printf( "%.5f\n", answer*100 );
    }

   }
}

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;