首页 > ACM题库 > HDU-杭电 > HDU 3455-Leap Frog-动态规划-[解题报告]HOJ
2014
03-23

HDU 3455-Leap Frog-动态规划-[解题报告]HOJ

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个位置所需要的最少跳跃次数。

可以YY dp[i][j]=min{dp[k][i]+1},要达到dp[i][j]这个状态,肯定要是从某一个位置k 通过i位置跳到j位置,由于N可达100000,注意到每次跳跃的范围最大只能为10,所以最多只需要保留前十个位置的状态就可以了

【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;
}

参考:http://hi.baidu.com/abcdcamey/item/7ad87ef3e048460dd89e72b4