sgu 221

Posted on 2010-12-07 20:33 王之昊 阅读(304) 评论(0)  编辑 收藏 引用 所属分类: sgu
这是黑书上的一道例题(P243),在一个n*n的国际象棋棋盘上,放k只象,有多少种方法使得象之间不会攻击。

首先第一个观察是白色格子和黑色格子是独立的,可以分开考虑,注意二者不一定对称。然后旋转棋盘,得到一个菱形的期盼,注意到行列顺序是无关的,所以可以交换行列,从小到大开始dp。

附录一:accept代码(dp)
 1 //dp,黑书P243
 2 
 3 import java.util.Scanner;
 4 import java.util.*;
 5 import java.math.BigInteger;
 6 
 7 class biShop{
 8     int n, k;
 9     biShop(int _n, int _k){
10         n = _n;
11         k = _k;
12     }
13     
14     BigInteger [] countOneSide(Vector<Integer> upper){
15         int [] upp = new int[upper.size()];
16         for(int i = 0; i < upp.length; i++){
17             upp[i] = upper.get(i);
18         }
19         Arrays.sort(upp);
20         
21         BigInteger [] pre, now;
22         now = new BigInteger[1]; 
23         now[0= BigInteger.ONE;
24         
25         for(int i = 0; i < upp.length; i++){
26             pre = now;
27             now = new BigInteger[ upp[i] + 1 ];
28             for(int j = 0; j < now.length; j++){
29                 now[j] = BigInteger.ZERO;
30                 if( j < pre.length )
31                     now[j] = now[j].add( pre[j] );
32                 if0 < j && j <= pre.length)
33                     now[j] = now[j]. add( pre[j-1].multiply(BigInteger.valueOf(upp[i] - j + 1)) );
34             }
35         }
36         return now;
37     }
38     
39     BigInteger count(){
40         Vector<Integer> A = new Vector<Integer>();
41         Vector<Integer> B = new Vector<Integer>();
42         
43         A.add(n);
44         for(int i = n-1, j = 0; i > 0; i--, j++){
45             if( (j & 1== 0){
46                 B.add(i);
47                 B.add(i);
48             }else{
49                 A.add(i);
50                 A.add(i);
51             }
52         }
53         
54         BigInteger [] a = countOneSide(A);
55         BigInteger [] b = countOneSide(B);
56         BigInteger res = BigInteger.ZERO;
57         
58         for(int i = 0; i <= k; i++){
59             if(i >= a.length || k - i >= b.length)continue;
60             res = res.add( a[i] .multiply( b[k-i]) );
61         }
62         return res;
63     }
64 }
65 
66 public class Solution{
67     public static void main(String[] args)throws Exception{
68         Scanner sc = new Scanner(System.in);
69         
70         biShop b = new biShop( sc.nextInt(), sc.nextInt() );
71         
72         System.out.println( b.count() );
73     }    
74 }




只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊