机智的CSY (HGOI 2019.2.15 T3)

2019-02-15 14:39:54


题目大意:

在数轴正半轴上有两个点,a,b,可以-1,+1,*2,问需要多少部能使a变成b

数据范围:

小于10000

做法一:

已经见过无数遍了这道题目。。。

那么首先就是想到的DP了

用f[i]表示到i要多少步。对于小于a的数,步数减过去就行了,大于a的,$f[i]=min(f[i-1]+1,f[(i+1)/2]+1+i\mod2)$。可以简单的知道,$k*2$的步数要比$k*2+1$的步数少1,所以$k*2$和$k*2-1$的步数是一样的。对于大于a的偶数,显然是从a/2转移的。但是对于奇数,你是从$(a+1)/2$转移还是$a/2$直接转移呢?当然都要转移啦!但是,显然,对于奇数,$f[i-1]+1$和$f[i/2]+2$的情况是一样的啊,都是先转移到i-1在加过来。所以转移方程可以简单的写成一句话就是$f[i]=min(f[i-1]+1,f[(i+1)/2]+1+i\mod2)$

然后程序。。超级短

#include<cstdio>
using namespace std;
int a,b;
int f[200100];
int main()
{
    scanf("%d%d",&a,&b);
    for(int i=a-1;i>=0;i--)
        f[i]=f[i+1]+1;
    for(int i=a+1;i<=200100;i++)
        f[i]=min(f[i-1]+1,f[(i+1)/2]+1+i%2);
    printf("%d",f[b]);
    return 0;
}

做法二

你当然也可以去dfs啊,bfs啊,spfa啊,随你喜欢啦。。