首页 > 代码库 > UVa 10328 Coin Toss(Java大数+递推)

UVa 10328 Coin Toss(Java大数+递推)

 

https://vjudge.net/problem/UVA-10328

题意:

有H和T两个字符,现在要排成n位的字符串,求至少有k个字符连续的方案数。

 

思路:
这道题目和ZOJ3747是差不多的,具体做法可以参考另一篇博客http://www.cnblogs.com/zyb993963526/p/7203833.html

但是这道题目的话是要用大数来做的,c++感觉不太好写,就学了下java的做法。

 1 import java.math.BigInteger; 2 import java.util.Scanner; 3  4 public class Main{ 5     public static int n; 6     public static BigInteger d[][]=new BigInteger[105][2]; 7      8     public static BigInteger compute(int u){ 9         d[0][0]=BigInteger.valueOf(0);10         d[0][1]=BigInteger.valueOf(1);11         for(int i=1;i<=n;i++){12             BigInteger sum = d[i-1][0].add(d[i-1][1]);13             d[i][1]=sum;14             15             if(i<=u)  d[i][0]=sum;16             else if(i==u+1)  d[i][0]=sum.subtract(BigInteger.valueOf(1));17             else d[i][0]=sum.subtract(d[i-u-1][1]);18         }19         return d[n][0].add(d[n][1]);20     }21     22     public static void main(String[] args){23         int k;24         Scanner in=new Scanner(System.in);25         while(in.hasNext()){26             n=in.nextInt();27             k=in.nextInt();28             System.out.println(compute(n).subtract(compute(k-1)));29         }30         in.close();31     }32 }

 

UVa 10328 Coin Toss(Java大数+递推)