题解 P1748 【H数】

# 我来讲讲 $dp$ 的做法 ## 前言 昨天 $PHY$ 大佬问我，这题怎么做？考虑到他没学过 $set$ 、 $priority_queue$ 和 $queue$ 。之后，我就想到了可以用 $dp$ 来解决这道题。 ## 正文 ### 设置状态 很显然，我们可以用 $f[i]$ 表示第$i$个数是多少。 ### 转移 第$i$个$H$数是多少，我们显然应该从前面的$i-1$个数去分别$\times2$、$\times3$、$\times5$、$\times7$中取比第$i-1$个$H$数大的最小数。 ### 边界条件 $f_1=1$是很显然的 此外还要注意$f_0=0$ ### 代码 我们现在就可以开始写代码了 **注意开$long$ $long$** ```cpp #include <bits/stdc++.h> using namespace std; template<typename T>inline void read(T &FF){ T RR=1;FF=0;char CH=getchar(); for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1; for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48); FF*=RR; } template<typename T>void write(T x){ if(x<0)putchar('-'),x*=-1; if(x>9)write(x/10); putchar(x%10+48); } long long f[10010]; int main(){ memset(f,127,sizeof(f));//为了找最小，我们最开始就得赋成最大 int n; read(n); f[0]=0;//初始化 f[1]=1;//初始化 for(int i=2;i<=n;i++) for(int j=i-1;j>=1;j--) if(f[j]*2>f[i-1])f[i]=min(f[i],f[j]*2); else if(f[j]*3>f[i-1])f[i]=min(f[i],f[j]*3); else if(f[j]*5>f[i-1])f[i]=min(f[i],f[j]*5); else if(f[j]*7>f[i-1])f[i]=min(f[i],f[j]*7); else break;//优化 write(f[n]);//输出 return 0; } ``` ## 后记 这个代码还是很简短的，十分好写，希望大家以后学习也能好好想想一题多解 最后来求一下赞和评论！