fafu 1411

想了好久都没想到怎么去判断当分类dp的时候大于或者等于要求的 值时应该怎么半 后来经过停了 qlx的想法 然后就 敲了出来

这题说的是 一个整数 分解成几个素数的和  按这个数的含有的最大素数 进行排列给定的一个数 小于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
",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
",ber[T-1]);
    }
     return 0;
}