机智的CSY （HGOI 2019.2.15 T3）
hicc0305
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啊，随你喜欢啦。。