2010年02月23日星期二.sgu269 dp
此题和
220 Little Bishops
221 Big Bishops
基本是一样的，只不过更直接一点
要用高精度加法和乘法，所以我用c++写了个大数，弄了好几次，调了半天精度，
用滚动数组优化才过的。。。还是java大数快啊，
注意要先将输入的n个数排序，然后用递推式
This task is almost same as
220 Little Bishops
221 Big Bishops
But,it is easier than those two.
This task need Big Integer addition and multiplication,I practice writing Bignum in
c++.I changed the static array size several times,and use rolling array to get
Accepted.Due to the brief form of dp,I wrote in java again,that is easier and
quicker...
initial: dp[0][0] = 1;
for(i = 1;i <= n;i++) {
dp[i][0] = dp[i-1][0];
for(j = 1;j <= num[i] && j <= k;j++) {
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (num[i] - j + 1);
}
}
1002871 23.02.10 10:33 schindlerlee 269 .CPP Accepted 868 ms 1191 kb
1002870 23.02.10 10:32 schindlerlee 269 .JAVA Accepted 127 ms 2555 kb
c++代码
1
2 const int N = 256;
3 int n, k, num[N];
4 struct bignum {
5 int s[600], len;
6 bignum() {
7 memset(s, 0, sizeof(s));
8 len = 1, s[0] = 0;
9 } bignum(int a) {
10 memset(s, 0, sizeof(s));
11 len = 0;
12 while (a > 0) {
13 s[len++] = a % 10;
14 a /= 10;
15 }
16 }
17 }
18 //http://www.cppblog.com/schindlerlee
19 pool[2][N], *prev, *next;
20 bignum int2bignum(int a) { return bignum(a); }
21 void pr(bignum a)
22 {
23 if (a.len == 0) {
24 printf("0\n");
25 return;
26 }
27 for (int i = a.len - 1; i >= 0; i--) {
28 printf("%d", a.s[i]);
29 }
30 }
31
32 bignum operator +(bignum a, bignum b)
33 {
34 int len = max(a.len, b.len), i;
35 for (i = 0; i < len; i++) {
36 a.s[i] += b.s[i];
37 }
38 for (i = 0; i < len; i++) {
39 if (a.s[i] >= 10) {
40 a.s[i] -= 10;
41 a.s[i + 1] += 1;
42 }
43 }
44 a.len = len;
45 while (a.s[a.len] > 0) {
46 a.len++;
47 }
48 return a;
49 }
50
51 bignum operator *(bignum a, int b)
52 {
53 int i, shift = 0;
54 for (i = 0; i < a.len; i++) {
55 a.s[i] *= b;
56 }
57 for (i = 0; shift > 0 || i < a.len; i++) {
58 a.s[i] += shift, shift = 0;
59 if (a.s[i] >= 10) {
60 shift = a.s[i] / 10;
61 a.s[i] %= 10;
62 }
63 }
64 a.len = i;
65 assert(a.s[a.len] == 0);
66 return a;
67 }
68
69 int main()
70 {
71 int i, j;
72 scanf("%d%d", &n, &k);
73 for (i = 1; i <= n; i++) {
74 scanf("%d", num + i);
75 }
76 sort(num + 1, num + 1 + n);
77
78 prev = pool[0], next = pool[1];
79 prev[0] = int2bignum(1);
80 for (i = 1; i <= n; i++, swap(prev, next)) {
81 next[0] = prev[0];
82 for (j = 1; j <= num[i] && j <= k; j++) {
83 next[j] = prev[j] + (prev[j - 1] * (num[i] - j + 1));
84 }
85 }
86 pr(prev[k]);
87 putchar(10);
88 return 0;
89 }
java 代码
1 import java.util.*;
2 import java.math.*;
3 import java.io.*;
4 //http://www.cppblog.com/schindlerlee
5 public class Solution {
6 public static void main(String[] args) {
7 Scanner cin = new Scanner(
8 new BufferedReader(
9 new InputStreamReader(System.in)));
10 int i, j, n, k;
11 BigInteger dp[][] = new BigInteger[251][251];
12 int num[] = new int[256];
13 n = cin.nextInt();
14 k = cin.nextInt();
15 for (i = 1; i <= n; i++) {
16 num[i] = cin.nextInt();
17 }
18 for (i = 0; i < 251; i++) {
19 for (j = 0; j < 251; j++) {
20 dp[i][j] = BigInteger.ZERO;
21 }
22 }
23 Arrays.sort(num,1,n+1);
24 dp[0][0] = BigInteger.ONE;
25 for (i = 1; i <= n; i++) {
26 dp[i][0] = dp[i - 1][0];
27 for (j = 1; j <= k && j <= num[i]; j++) {
28 dp[i][j] = dp[i - 1][j].add(dp[i - 1][j - 1].
29 multiply(BigInteger.valueOf(num[i] - j + 1)));
30 }
31 }
32 System.out.println(dp[n][k]);
33 }
34 }
35