SGU 106.Index of super-prime

时间限制：0.25s

空间限制：4M

题目大意：

在从下标1开始素数表里，下标为素数的素数，称为超级素数（Super-prime），给出一个n(n<=10000)，求最少能用几个超级素数的和表示，并以降序输出这些超级素数。

Sample Input

Sample Output

3 3

{=============}

分析：

读入n以后，先将不大于n的Super-prime筛出，然后DP

简单点的直接用完全背包DP，

稍微优化一点，减少一半的循环次数的话

用 F[i]=max(f[i],f[j]+f[i-j]);

其它细节要动手做了才知道。

参考代码：

#include <iostream>

#include <cstring>

using namespace std;

int prime[11000], pd[11000], tol, sPrime[1000], sum;

int f[11000][3], n;

void init() {

	for (int i = 2; i <= n; i++) {

		if (!pd[i]) {

			prime[++tol] = i;

			for (int j = i + i; j <= n; j += i)   pd[j] = 1;

		}

	}

	for (int i = 2; i <= tol; i++)

		if (!pd[i]) sPrime[++sum] = prime[i];

	memset (pd, 0, sizeof pd);

	for (int i = 1; i <= sum; i++)

		pd[sPrime[i]] = 1;

}

void write (int x) {

	if (f[x][0] == 1) cout << x << ' ';

	else

		write (f[x][2]), write (f[x][1]);

}

int main() {

	cin >> n;

	init();

	for (int i = 3; i <= n; i++) {

		if (pd[i]) f[i][0] = 1;

		else {

                for (int j = 3; j <= i / 2 + 1; j++){

                    if (f[j][0] && f[i - j][0] &&

                       (f[i][0] == 0 || f[i][0] > f[j][0] + f[i - j][0])){

                       f[i][0] = f[j][0] + f[i - j][0];

                       f[i][1] = j, f[i][2] = i - j;

                    }

		}

		}

	}

	cout << f[n][0] << endl;

	if (f[n][0])  write (n);

	return 0;

}

http://www.cnblogs.com/keam37/ keam所有转载请注明出处

巴特西

SGU 106.Index of super-prime

最新文章

热门文章