首页 > 代码库 > 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大数+递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。