1 条题解

  • 1
    @ 2023-8-20 9:32:37
    #include <stdio.h>
    #include <string.h>
    
    const int MaxLen=20000;
    const int InitNum=0x3f;
    
    
    int min(int a1,int a2)
    {
        return a1>a2?a2:a1;
    }
    
    void printAns(int* priceArray,int k,int max)
    {
         for(int i=0;i<k;i++)
        {
            if(i>0)
            {
                printf(" ");
            }
            printf("%d",priceArray[i]);
        }
        printf("\n");
        printf("MAX=%d\n",max);
    }
    
    //动态规划求出最大可以表示面值
    int getMaxSize(int* priceArray,int priceLen,int * dpArray,int n)
    {
        int size=MaxLen*4;
        memset(dpArray,InitNum,size);
        int i,j;
        dpArray[0]=0;
        for(i=1;i<=priceLen;i++)
        {
            int num=priceArray[i-1];
            dpArray[num]=1;
            for(j=num+1;j<=n*num;j++)
            {
                dpArray[j]=min(dpArray[j],dpArray[j-num]+1);
                //最后一位不需要全部求解 减少次数和数组消耗
                if(i==priceLen&&dpArray[j]>n)
                {
                    break;
                }
            }
        }
        for(i=1;i<MaxLen;i++)
        {
            if(dpArray[i]>n)
            {
                return i-1;
            }
        }
        return 1;
    }
    
    
    int* dps(int n,int k,int *dpArray,int& max)
    {
        int* priceArray=new int[k];
    
        priceArray[0]=1;
        max=n;
        if(k==1)
        {
            return priceArray;
        }
    
        int* tmpArray=new int[k];
        int* maxArray=new int[k];
        int i=1,j;
        tmpArray[0]=1;
        tmpArray[1]=2;
        maxArray[1]=n+1;
        while (i>0)
        {
            int tmpMax=getMaxSize(tmpArray,i+1,dpArray,n);
            // printAns(tmpArray,i+1,tmpMax);
            if(i==k-1)
            {
    
                if(tmpMax>max){
                    max=tmpMax;
                    for(j=0;j<k;j++)
                    {
                        priceArray[j]=tmpArray[j];
                    }
                }
    
                tmpArray[i]++;
                while (tmpArray[i]>maxArray[i])
                {
                    i--;
                    if(i==0)
                    {
                        break;
                    }
                    tmpArray[i]++;
                }
                
            }
            else{
                i++;
                maxArray[i]=tmpMax+1;
                tmpArray[i]=tmpArray[i-1]+1;
            }
        }
        
        delete maxArray;
        delete tmpArray;
        return priceArray;
    }
    
    int main(){
        int n,k;
        scanf("%d %d",&n,&k);
        int* dpArray=new int[MaxLen];
        int max=0;
        int * priceArray=dps(n,k,dpArray,max);
    
        printAns(priceArray,k,max);
        delete priceArray;
        delete dpArray;
        return 0;
    }
    
    
    
    • 1

    [NOIP1999 提高组] 邮票面值设计

    信息

    ID
    1757
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    26
    已通过
    20
    上传者