1 条题解
-
1
#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
信息
- ID
- 1757
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 28
- 已通过
- 22
- 上传者