安溪县住房和城乡建设网站,可以完成交易的网站 做,记账代理公司注册,广州免费公司注册这是我第一次模拟题测试点全部AC。。。 同机房的DALAO都用的BFS 然而我用的DP#xff08;其实不会BFS#xff09; 话不多说#xff0c;上题#xff01; #xff08;灰常详细#xff09;DP解法#xff1a; 重点还是状态转移方程式的推导 1个点i要么是后面的位置i-1往前走…这是我第一次模拟题测试点全部AC。。。 同机房的DALAO都用的BFS 然而我用的DP其实不会BFS 话不多说上题 灰常详细DP解法 重点还是状态转移方程式的推导 1个点i要么是后面的位置i-1往前走一步i1往后走一步即dg[i] 或者是一个点i*2从i瞬移一步。 如果是自身的话也可能不走。 此时就要找哪一种走的最少了 状态转移方程就是dg[i]min(dg[i],min(dg[i-1]1,dg[i1]1)) 和dg[i*2]min(dg[i*2],dg[i]1) 推导出方程就比较容易解了 #includecstring
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
int dp[2000005];//数组开两倍是因为有可能走到K点后面再往前走。
int main()
{freopen(meet.in,r,stdin);freopen(meet.out,w,stdout);int N,K;scanf(%d%d,N,K);memset(dp,0x7f,sizeof(dp));//将所有数初始化到最大值dp[N]0;//从N开始步数为0for(int iN-1;i0;i--)//先往前推把前面的步数通过dp[N]算出来{dp[i]min(dp[i],(dp[i-1]1,dp[i1]1));dp[i*2]min(dp[i*2],dp[i]1);}for(int iN;iK;i)//再往后推计算后面的步数。{dp[i]min(dp[i],min(dp[i-1]1,dp[i1]1));dp[i*2]min(dp[i*2],dp[i]1);}coutdp[K]; //打印K点的步数。return 0;
} 看起来还是挺简单的 我再去研究一下广搜做法。。。 转载于:https://www.cnblogs.com/JCRL/p/9913684.html
