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的时候结束。

输出：
输出最少所需要的到达终点再返回原点的总步数

样例输入：
6
3 5 3 2 6 5
0

样例输出：
7

//////// 写了下面的东西，干脆就帖出来了

ct5_2 解题DP方法

例如数据：
6
3 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;
}

评论