这题说的是 一个整数 分解成几个素数的和 按这个数的含有的最大素数 进行排列给定的一个数 小于200 求这个数的 第k大的数是什么,然后让你计算出 第k大是组成数是什么.
分类进行dp 比如起始位进行dp 分类进行的dp可以按照从小到大的排列进行 大的数 只能用比他小的数 进行dp 类似于完全背包,这样在查找的时候也分类进行查找记得从大到小查找ok
#include <iostream>
#include<cstdio>
#include<string.h>
using namespace std;
bool a[300];
int p[50],dp[50][300],ber[100];
void prime()
{
int count=0;
memset(a,0,sizeof(a));
for(int i=2;i<=201;i++)
{
if(a[i]==0){p[count++]=i;}
for(int j=0,k;j<count&&(k=p[j]*i)<=201;j++)
{
a[k]=1;
if(i%p[j]==0) break;
}
}
//for(int i=0;i<count;i++)
// printf("%d ",p[i]);
}
int work(int n,int k,int H)
{
int count=0;
for(int i=H;i>=0;i--)
{
if(dp[i][n]<k)
k-=dp[i][n];
else if(dp[i][n]>=k)
while(dp[i][n]>=k)
{
ber[count++]=p[i];
n-=p[i];
if(dp[i][n]<k)
{
k-=dp[i][n];
break;
}
if(k==0||n==0) break;
}
if(k==0||n==0) break;
}
return count;
}
int main()
{
//eopen("data.txt","r",stdin);
prime();
int n,k,H,sum;
int i,j;
while(scanf("%d%d",&n,&k)==2)
{
sum=0;
memset(dp,0,sizeof(dp));
if(!n&&!k) break;
for(i=0;i<46;i++)
{
if(p[i]>n) {H=i;break;}
dp[i][p[i]]=1;
int st=p[i];
for( j=i;j>=0;j--)
{
for(int g=st+p[j];g<=n;g++)
if(dp[g-p[j]]!=0)
{
dp[i][g]+=dp[i][g-p[j]];
}
}
sum+=dp[i][n];
}
printf("%d\n",sum);
if(k>sum)k=sum;
int T=work(n,k,H);
printf("%d=",n);
for(i=0;i<T-1;i++)
printf("%d+",ber[i]);
printf("%d\n",ber[T-1]);
}
return 0;
}