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.shnenglu.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.shnenglu.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?