ct5_2: 跳棋★★ 题目描述：水平方向上有n个格子，格子上写着1到n的数字中的一个，游戏规则是：走到某一格，上面的数字假如是s，则可以选择跳到第s个格子或者前进一格，问你最少要走多少步才能到达最后一格并且返回起点。如：3 5 3 2 6 5 ，你去的时候可以一步一步到终点(5步)，也可以一开始就跳到第三格，再一步一步到终点(4步)，或者先前进一步再跳到第5格再一步一步地走(3步)，最少是3步到达。然后要再返回的时候，最少步数的走法是，左移两步再跳到第二格再左移一步(4步)，共7步。 输入：多组测试数据，第一行是一个整数n(1<=n<=1e5)，第二行是n个整数，表示对应的格子上写着的数。当n输入为0的时候结束。 输出：输出最少所需要的到达终点再返回原点的总步数 样例输入：63 5 3 2 6 50 样例输出：7 //////// 写了下面的东西，干脆就帖出来了 ct5_2 解题DP方法 例如数据：63 5 3 2 6 5 设两个数组： data[] = 3 5 3 2 6 5另设一个用于DP Dp[],Dp[n]表示从n位置到达终点需要走的最少的步数 首先，从终点 n=6 开始，终点到终点需要 0 步,所以设Dp[6]=0然后n--,即 n=5，n=5到达终点需要 1 步，设Dp[5]=1 到此Dp[]数组初始化完毕 n--,此时 n=4因为 data[4] <= 4 因此这里不能往终点方向跳只能向前一步,Dp[4] = Dp[5]+1 = 2同里Dp[3] = Dp[4]+1 = 3 Dp[2]，因为data[2] = 5 > 2 所以可以跳到第五个位置，这里需要决策，从两种方法里选一种，如果往前一步，则到达终点最少需要 Dp[3]+1 = 4 步而跳到第五个位置，则需要 Dp[5]+1= 2,显然选择 Dp[2] = Dp[5]+1 = 2 同理Dp[1]=Dp[2]+1 = 3; 因此从起始点到终点最少需要 Dp[1] = 3 步 从终点回到起点是一样的方法。data[] = 3 5 3 2 6 5         1 2 3 4 5 6往前走Dp[] = 3 2 3 2 1 0 ///// my Code #include <stdio.h>#define MAX 100010 int data[MAX];int Dp[MAX]; int main(){ int sum,i,a,t; while(scanf("%d",&a)!=EOF && a!=0){  for(i=1; i<=a; i++)   scanf("%d",&data[i]);  for(Dp[a]=0,i=a-1; i > 0; i--){   t = data[i]>i ? 1+Dp[data[i]] : MAX;   Dp[i] = Dp[i+1]+1<t ? Dp[i+1]+1 : t;  }  sum = Dp[1];  for(Dp[1]=0,i=2; i <= a; i++){   t = data[i]<i ? 1+Dp[data[i]] : MAX;   Dp[i] = Dp[i-1]+1<t ? Dp[i-1]+1 : t;  }  printf("%d\n",sum+Dp[a]); } return 0;}

评论