2014
03-23

# Leap Frog

Jack and Jill play a game called “Leap Frog” in which they alternate turns jumping over each other. Both Jack and Jill can jump a maximum horizontal distance of 10 units in any single jump. You are given a list of valid positions x1,x2,…, xn where Jack or Jill may stand. Jill initially starts at position x1, Jack initially starts at position x2, and their goal is to reach position xn.Determine the minimum number of jumps needed until either Jack or Jill reaches the goal. The two players are never allowed to stand at the same position at the same time, and for each jump, the player in the rear must hop over the player in the front.

The input file will contain multiple test cases. Each test case will begin with a single line containing a single integer n (where 2 <= n <= 100000). The next line will contain a list of integers x1,x2,…, xn where 0 <=x1,x2,…, xn<= 1000000. The end-of-fi le is denoted by a single line containing “0″.

The input file will contain multiple test cases. Each test case will begin with a single line containing a single integer n (where 2 <= n <= 100000). The next line will contain a list of integers x1,x2,…, xn where 0 <=x1,x2,…, xn<= 1000000. The end-of-fi le is denoted by a single line containing “0″.

6
3 5 9 12 15 17
6
3 5 9 12 30 40

3
-1

【分类】：DP

【题目大意】：给定一个从小到大的正整数序列表示位置，刚开始A在序列中第一个元素位置，B在序列中第二个元素位置，接下来A要跳到B的后一个位置，且跳跃的距离不能超过10，跳跃的距离定义为序列中整数之差。求其中一人到达最后一个位置时，两人跳跃的总次数最少，N<=100000;

【思路】：首先想到的是普通的DP，dp[i][j]表示一个人在第i个位置，另一个人在第j个位置所需要的最少跳跃次数。

【KEY】：要运用题目的信息，达到空间上的优化

【代码】

#include<stdio.h>
#include<string.h>
int dp[12][100005];
int a[100005];
int MIN(int a,int b)
{
if(a<b)
return a;
return b;
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
int i,j,k;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,-1,sizeof(dp));
dp[1][2]=0;
for(i=3;i<=n;i++)
{
for(j=1;j<=10;j++)
{
if(a[i]-a[i-j]<=10)
{
for(k=1;k<=10;k++)
{
if(a[i]-a[i-j-k]<=10)
{
if(dp[k][i-j]!=-1)
{
if(dp[j][i]==-1)
{
dp[j][i]=dp[k][i-j]+1;
}
else
{
dp[j][i]=MIN(dp[j][i],dp[k][i-j]+1);
}
}
}
}
}
else
break;
}
}
int ans=1000000000;
for(i=1;i<=10;i++)
{
if(dp[i][n]!=-1)
{
ans=MIN(dp[i][n],ans);
}
}
if(ans!=1000000000)
printf("%d\n",ans);
else
printf("-1\n");
}
return 0;
}