学步园

这个题要求对一个数，将起表示为超级素数的和，超级素数是这样一类素数，他们在素数序列中的下标也是素数。

我们现用筛法求出10000以内的超级素数。然后做一次完全背包，最后将结果输出就可以了。一直WA on 8。

都无语了，后来仔细看了一边题目才发现，原来要输出 non-incresing order 我一直输出升序。原来前面的测试

数据可能都是1个或者没有答案的。以后读题要更仔细。。。。－.-b#include "iostream"<br /> #include "cstring"<br /> #include "algorithm"<br /> #include "vector"<br /> using namespace std;<br /> const int MaxPrime = 10001;<br /> const int INF = 0x7ffffffe;<br /> bool isprime[MaxPrime];<br /> vector<int> primeList;<br /> vector<int> superprime;<br /> vector<int> tt;<br /> pair<int,int> ans[MaxPrime];<br /> void Sieve(){<br /> int i,j,k;<br /> memset(isprime,true,sizeof(isprime));<br /> isprime[0] = isprime[1] = false;<br /> primeList.push_back(2);<br /> for(i = 3;i < MaxPrime;i += 2){<br /> if(i*i > MaxPrime) break;<br /> if(isprime[i]){<br /> primeList.push_back(i);<br /> for(j = i * i ,k = 2 * i;j < MaxPrime; j += k)<br /> isprime[j] = false;<br /> }<br /> }<br /> for(;i < MaxPrime; i+=2)<br /> if(isprime[i]) primeList.push_back(i);<br /> memset(isprime,true,sizeof(isprime));<br /> isprime[0] = isprime[1] = false;<br /> i = 2;<br /> for(int j = i * 2;j < MaxPrime; j += i)<br /> isprime[j] = false;<br /> for(i = 3;i < MaxPrime; i+=2){<br /> for(j = i *2; j < MaxPrime;j += i)<br /> if(isprime[j])<br /> isprime[j] = false;<br /> }<br /> for(i = 0 ;i < primeList.size();++i)<br /> if(isprime[i + 1]) superprime.push_back(primeList[i]);<br /> }<br /> void calc(){<br /> for(int i = 0 ;i < MaxPrime; ++i)<br /> ans[i].first = INF;<br /> ans[0].first = 0;<br /> for(int i = 0 ;i < superprime.size(); ++i){<br /> for(int v = superprime[i]; v < MaxPrime; ++v){<br /> if(ans[v- superprime[i]].first + 1 < ans[v].first){<br /> ans[v].first = ans[v - superprime[i]].first + 1;<br /> ans[v].second = superprime[i];<br /> }<br /> }<br /> }<br /> }<br /> void trace(int num){<br /> if(num == 0)<br /> return;<br /> else{<br /> tt.push_back(ans[num].second);<br /> trace(num - ans[num].second);<br /> }<br /> }<br /> int main(){<br /> Sieve();<br /> calc();<br /> int N;<br /> scanf("%d",&N);<br /> if(ans[N].first != INF){<br /> trace(N);<br /> sort(tt.begin(),tt.end());<br /> printf("%d/n",ans[N].first);<br /> for(int i = ans[N].first-1 ;i >=0; --i)<br /> printf("%d ",tt[i]);<br /> putchar('/n');<br /> }else printf("0/n");<br /> return 0;<br /> }