Posted on 2010-12-07 20:33
王之昊 阅读(305)
评论(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 if( 0 < 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 }