ZHK

ZHK

一只叫ZHK的蒟蒻为了RP而战

题解 P1748 【H数】

posted on 2020-01-26 11:42:51 | under 题解 |

我来讲讲 $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$

#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;
}

后记

这个代码还是很简短的,十分好写,希望大家以后学习也能好好想想一题多解

最后来求一下赞和评论!