USACO邮票丑数题解

这两道题可使用特殊的优化方法：

丑数：

#include

#include

#include

using namespace std;

int num[51];

int f[5000001];

int k,n,m,ans;

int tot[201]={0};//表示第j个数的值乘上第f[tot[j]]大于当前寻找的丑数的前一个丑数的最小值

bool comp(int a,int b){

       return a

}

int main(){

       scanf("%d%d",&k,&n);

       for(int i=0;i

              scanf("%d",&num[i]);//读入

       }

       f[0]=1;//将一视为第0个丑数

       //sort(num,num+n,comp);

       //f[1]=num[0];

       for(int i=1;i<=n;i++){//i表示第i个丑数

              m=0x7fffffff;//为比较数m附上极大值

              for(int j=0;j

                     while(num[j]*f[tot[j]]<=f[i-1])//寻找j个数的值乘上第f[tot[j]]大于当前寻找的丑数的前一个丑数的最小值

                   tot[j]++; 

                     f[i]=f[tot[j]]*num[j];

                     m=min(m,f[i]);//比较哪一个m更小

              }

              f[i]=m;//第i个丑数

       }

       printf("%d",f[n]);//输出

return 0;

}

同理邮票有着相似的代码

但是邮票数据时间给的非常卡所以有以下省时方式：

——对邮票价值进行快排使之降序排序，在寻找时就可以提前断点。

邮票：#include

#include

#include

using namespace std;

int num[51];

int f[5000001];//到达值的最小邮票张数

int k,n,m,ans;

bool comp(int a,int b){

       return a

}

int main(){

       scanf("%d%d",&k,&n);

       for(int i=0;i

              scanf("%d",&num[i]);

       }

       sort(num,num+n,comp);

       for(int i=1;;i++){//直到生成完毕再退出

              m=1000000007;//极大值

              for(int j=0;j

                     if(i省时方式因为后面一定I于是断点

                            break;

                     f[i]=f[i-num[j]]+1;

                     m=min(m,f[i]);//寻找到达该值的最小邮票张数

              }

              f[i]=m;

              if(f[i]>k){//生成完毕

                     ans=i-1;

                     break;

              }

       }

       printf("%d",ans);

}

切勿使用流输出输入此题用此法非常耗时：

可见第三个点子过得勉强。

完；

 

Designed by Leo JAM