首页 > 代码库 > zoj 2414 - Index of Prime
zoj 2414 - Index of Prime
题目:判断一个数能不能写成素数的和的形式,输出对应的素数大小最小组合。
分析: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\n%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("\n"); } return 0; }
zoj 2414 - Index of Prime
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。