ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 递规算法

递规算法

原创 Linux操作系统 作者:it01 时间:2019-06-14 22:03:04 0 删除 编辑
  1. import java.util.BitSet;
  2. public class BTGame{
  3. private static final int MAX = 500;
  4. private static BitSet isSuit =new BitSet(offset(MAX+1)), isSolved =new BitSet(offset(MAX+1));
  5. static{
  6. for(int k=0;k<=MAX;k++){isSuit.set(offset(k)); isSolved.set(offset(k));}
  7. }
  8. private static int offset(int n){ //表示第n个的起始位置
  9. return n*(n-1)*(n-2)/6 + n;
  10. }
  11. public static boolean isSuit(int n,int k){
  12. if(k<0||k>n*(n-1)/2) return false;
  13. int off =offset(n);
  14. if(isSolved.get(off+k)) return isSuit.get(off+k);
  15. for(int i =1;i
  16. if(isSuit(n -i,k -i*(n-i) ) ){
  17. isSolved.set(off +k);
  18. isSuit.set(off +k);
  19. return true;
  20. }
  21. isSolved.set(off +k);
  22. return false;
  23. }
  24. public static void test(int n,int k){
  25. System.out.println(isSuit(n,k)?"YES":"NO");
  26. }
  27. public static void main(String[] args){
  28. test(2,0);
  29. test(2,1);
  30. test(3,1);
  31. test(3,2);
  32. test(5,4);
  33. test(5,5);
  34. }
  35. }

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/12467/viewspace-148154/,如需转载,请注明出处,否则将追究法律责任。

下一篇: DP算法解释
请登录后发表评论 登录
全部评论

注册时间:2002-05-25

  • 博文量
    489
  • 访问量
    371356