zoj 2414 - Index of Prime
來源：程序員人生 發(fā)布時間：2014-10-13 03:51:22 閱讀次數(shù)：3486次
題目：判斷一個數(shù)能不能寫成素數(shù)的和的形式，輸出對應(yīng)的素數(shù)大小最小組合。
分析：dp，多重背包。看到整數(shù)拆分就是背包了。
由于時間和數(shù)據(jù)的限制，所以采用打表計算；
每次記錄上次使用的 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;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
