Posted on 2008-02-09 14:48
oyjpart 閱讀(1745)
評論(0) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
1
long long dp[500001];
2bool p[500001];
3
4void pre() {
5 memset(p, 0, sizeof(p));
6 p[0] = p[1] = 1;
7 int i, j;
8 for(i = 2; i < 500001; ++i) if(!p[i]) {
9 for(j = i+i; j < 500001; j+=i) {
10 p[j] = 1;
11 }
12 }
13}
14
15class PrimeSums
16{
17public:
18 long long getCount(vector <int> bag)
19 {
20 pre();
21
22 map<int, int> mm;
23 sort(bag.begin(), bag.end());
24 int i, j, k;
25 for(i = 0; i < sz(bag); ++i) {
26 if(mm.count(bag[i]))
27 mm[bag[i]]++;
28 else mm[bag[i]] = 1;
29 }
30 memset(dp, 0, sizeof(dp));
31 if(mm.begin()->first == 0) {
32 dp[0] = mm.begin()->second+1;
33 mm.erase(0);
34 }
35 else
36 dp[0] = 1;
37 for(map<int, int>::iterator it = mm.begin(); it != mm.end(); ++it) {
38 printf("%d %d\n", it->first, it->second);
39 int w = it->first;
40 for(j = 500000; j >= 0; --j) {
41 for(k = 1; k <= it->second; ++k) {
42 if(j-k*w >= 0) dp[j] += dp[j-k*w];
43 }
44 }
45 }
46 long long ans = 0;
47 for(i = 0; i < 500001; ++i) {
48 if(!p[i]) {
49 ans += dp[i];
50 if(dp[i]!=0) printf("dp[%d] = %d\n", i, dp[i]);
51 }
52 else if(dp[i]!=0) printf("dp[%d] = %d\n", i, dp[i]);
53 }
54 return ans;
55 }
56};
57
Rating 小漲，沒到黃。希望以后加油把Rating漲上去。