zoj 2414 - Index of Prime
来源：程序员人生 发布时间：2014-10-13 03:51:22 阅读次数：3337次
题目：判断一个数能不能写成素数的和的形式，输出对应的素数大小最小组合。
分析：dp，多重背包。看到整数拆分就是背包了。
由于时间和数据的限制，所以采用打表计算；
每次记录上次使用的 prime然后逆向求解即可。
说明：注意，没有时输出 0，由于没写 WA了好几次。。。（2011-10-03 18:37）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define OO 10001
bool used[ 10001 ];
int prime[ 1231 ];
int madelist()
{
memset( used, 0, sizeof( used ) );
int count = 0;
for ( int i = 2 ; i < 10000 ; ++ i )
if ( !used[ i ] ) {
prime[ ++ count ] = i;
for ( int j = i<<1 ; j < 10000 ; j += i )
used[ j ] = 1;
}
return count;
}
int f[ 10001 ];
int t[ 10001 ];
int main()
{
int C = madelist();
for ( int i = 0 ; i <= 10000 ; ++ i ) {
f[ i ] = OO;
t[ i ] = 0;
}
f[ 0 ] = 0;
for ( int i = 1 ; i <= C ; ++ i )
for ( int j = prime[ i ] ; j <= 10000 ; ++ j )
if ( f[ j ] > f[ j-prime[ i ] ]+1 ) {
f[ j ] = f[ j-prime[ i ] ]+1;
t[ j ] = prime[ i ];
}
int n;
while ( ~scanf("%d",&n) ) {
if ( t[ n ] ) {
printf("%d
%d",f[ n ],t[ n ]);
int v = n-t[ n ];
while ( t[ v ] ) {
printf(" %d",t[ v ]);
v = v-t[ v ];
}
}else printf("0");
printf("
");
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
