洛谷 题解 P1135 【奇怪的电梯】

大家都没有想到可以用DP做吗...

用f[i]表示从a楼去i楼所用的最少步数

目标：f[b]

初值：f[a]=0

转移：自己看代码，有注释

东芝电梯外呼显示P、那不就是一道大水题？？？

时间复杂度:O(n^2),AC！

空间就不说了，秀的可以

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int f[205],k[205];
int main() {int n,a,b;scanf("%d",&n);scanf("%d%d",&a,&b);//输入for(int i=1; i<=200; i++)f[i]=999999999;//initfor(int i=1; i<=n; i++)scanf("%d",&k[i]);//输入f[a]=0;//初值for(int j=1; j<=n; j++) {//枚举j次，保证正确性for(int i=1; i<=n; i++) {//枚举楼层if(i-k[i]>=1)f[i-k[i]]=min(f[i-k[i]],f[i]+1);if(i+k[i]<=n)f[i+k[i]]=min(f[i+k[i]],f[i]+1);//如果能到，就取更优值}}if(f[b]==999999999)printf("-1\n");//到不了else printf("%d\n",f[b]);//可以去return 0;
}