[AQX]贺老师的粉丝

题目描述

众所周知，贺老师是GXYZ典型的高富帅+学神。因此，贺老师拥有无数的粉丝。时光倒转到贺老师出生的那一天，贺老师仅有1个粉丝（接生他的医生）。但是，贺老师的粉丝显然不是仅仅只有1个的。

已知，贺老师的粉丝每天

要么增长i个（1<=i<=t）。

要么变成以前的k倍。

问：最早在第几天，贺老师的粉丝能够达到p个呢？(是恰好达到，不是超过)

输入输出格式

输入格式

一行，三个整数t,k,p，如题所述。

输出格式

一行，一个整数，代表最早的日子。

输入输出样例

输入样例1

1 2 10

输出样例1

5

解释：1-2-4-5-10，没有比这更快的了。

说明

【数据范围】

70%的数据，$$p \leq 10^5$$

100%的数据，$$p \leq 10^6​​，t,k \leq 1000$$

思路

dp

代码

dp

无优化：70；O2优化：90-100；

#include <bits/stdc++.h>
using namespace std;

int t,k,p;
int f[1000001];

int read()
{
    int sum=0,flag=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*flag;
}

int main()
{
//freopen("test.in","r",stdin); freopen("result.out","w",stdout); 
    memset(f,0x3f,sizeof(f));
    t=read(),k=read(),p=read();
    f[0]=0;
    f[1]=1;
    for(int i=2;i<=p;i++)
    {
        if(i%k==0)
        {
            if(f[i]>f[i/k]+1)    f[i]=f[i/k]+1;
        }
        for(int j=1;j<=t;j++)
        {
            if(i<=j)    break;
            else
            {
                if(f[i]>f[i-j]+1)    f[i]=f[i-j]+1;
            }
        }
    }
    cout<<f[p]<<endl;
    return 0;
}

STD

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <queue>
using namespace std;
long long t,k,p;
int fa[1000005];
int dis[1000005];
queue<long long> q;

int getfa(int x)
{
    if (fa[x]==x) return x;
    return fa[x]=getfa(fa[x]);
}
int main()
{
    cin>>t>>k>>p;
        for (int i=1;i<=p+1;i++)
            fa[i]=i;
        while (!q.empty()) q.pop();
        memset(dis,-1,sizeof(dis));
        dis[1]=1;
        fa[1]=2;
        q.push(1);
        while (!q.empty())
        {
            long long now=q.front();
            q.pop(); 
            for (int nex=getfa(now+1);nex<=min(p,now+t);nex=getfa(nex))
            {
                dis[nex]=dis[now]+1;
                q.push(nex);
                fa[nex]=nex+1;
            }
            if (now*k<=p && fa[now*k]==now*k)
            {
                dis[now*k]=dis[now]+1;
                q.push(now*k);
                fa[now*k]=now*k+1;
            }
        }
        cout<<dis[p]<<endl;
}