Problem description
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
Input
输入的第一行是一个整数T,测试数据的组数。对于每一组测试数据，第一行是一个正整数 L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
Output
对于每一组测试数据，输出一行只包括一个整数，表示青蛙过河最少需要踩到的石子数。
Sample Input
1
10
2 3 5
2 3 5 6 7
Sample Output
2
解题报告
这题因为 1 <= L <= 10^9 L非常大，只能进行状态压缩。如果 L小到可以开数组，我们可以设一个数组Dp[L_MAX]保存每个子状态，从后往前DP，Dp[n] 表示从坐标位置 n 跳到或者跳过终点的最优解(局部最优)，求Dp[n-1], Dp[n-1] = min{Dp(n-1+minJump ~ n-1+maxJump)}, minJump表示青蛙最小的跳数maxJump 表示青蛙最大的跳数，如果 n-1 位置有石头则 Dp[n-1]=Dp[n-1]+1，否则为 min{Dp(n-1+minJump ~ n-1+maxJump)}
比如对于示例：
10
2 3 5
2 3 5 6 7
首先我们初始化数组,Dp[]={0},从坐标位置7开始算,Dp[7]=min{Dp(2+7,3+7)}=0,因为7位置有石头所以Dp[7]=Dp[7]+1=1,同理,Dp[6]=1,Dp[5]=1,Dp[4] = min{Dp(4+2,4+3)} = min{Dp[6], Dp[7]} 为1, 因为5位置没有石头所以Dp[4]不用加1，最后可求得 Dp[] = {2,1,2,2,1,1,1,1,0,0,0 ……}, Dp[0]即为全局的最优解，表示从起点跳到或者跳过终点青蛙最少要踩到的石头数目。
这题因为L很大，子状态不能全部保存，我们观察到，当求Dp[n]的值时用到的状态只有
Dp(n+minJump, n+maxJump) 所以我们可以不用全部保存每个坐标位置的Dp值，而只要保存从n位置之后最多maxJump个坐标的Dp值即可。为此我们可设 Dp[maxJump]数组(对本题可设Dp[10])，我们可用一个变量nHeadStart跟踪坐标位置，当求n位置的Dp值时,nHeadStart=n+1。到这里我们解决了空间问题，真正难理解的是下面的状态压缩。
假如测试数据是:
1000000000
2 5 5
2 6 5 10 99999999
99999999这个位置的Dp值我们知道是 1，而该位置前面有99999999-10个位置都没有石头，我们不可能也没有时间去求所有这些中间位置的Dp值，但是10位置的值却与这中间的有关,How Can I do ??? 假如有这样一组Dp值,Dp[]={2 5 1 3} 我们观察到当 minJump != maxJump时，因为每次都取最小值所以经过有限步运算后，Dp={1 1 1 1}，即所有的Dp值都变成开始计算时的最小值。变化经过如下
数据：minJump=2, maxJump=3, Dp[]={2,5,1,3}
Dp[]={1,2,5,1} --- 解释：Dp[]={2,5,1,3} 从 5,1 里选，最小的为1 所以Dp 值变化为 {1,2,5,1}
Dp[]={2,1,2,5} --- 解释：Dp[]={1,2,5,1} 从 2,5 里选，最小的为2 所以Dp 值变化为 {2,1,2,5}
Dp[]={2,1,2,2} --- 解释：Dp[]={2,1,2,5} 从 1,2 里选，最小的为1 所以Dp 值变化为 {1,2,1,2}，后续步骤相同不在解释
Dp[]={1,2,1,2}
Dp[]={1,1,2,1}
Dp[]={1,1,1,2}
Dp[]={1,1,1,1}
即从当前位置到前面 7 个及 7 个以前的空位（没有石头），我们断定Dp[]={1,1,1,1}
因此,对 2 6 5 10 99999999,我们可以知道从 11 位置开始,Dp[]={0,0,0,0,0}（只需保存maxJump个）前面的就好做了。经过几步的空位可以达到稳定状态（我称Dp数组值不再变化的状态为稳定态），我们有两种方法
其一：每求一个空位后我们求Dp数组中的最值，如果最大和最小值相等就达到稳定态了。这种方法因为每次都要求最值，因此当maxJump比较大的时候不适合。
其二：我们可以断定如果当前位置之前至少有maxJump*maxJump个空位，就一定会出现稳定态（请读者自己理解) 这样我们遇到空位大于等于maxJump*maxJump时直接设Dp数组为最小值。
上面的是minJump != maxJump的情况，当minJump==maxJump时，假如Dp[]={0,0,1}
数据：minJump=3, maxJump=3,Dp[]={0,0,1},Dp的变化情况如下：
Dp[]={1,0,0}
Dp[]={0,1,0}
Dp[]={0,0,1}
Dp[]={1,0,0}
......
出现重复的情况，且min{Dp[]} != max{Dp[]},因此不能按minJump != maxJump的情况处理。这种情况只要将重复出现的位去掉即可,比如上面的如果当前位置前有 4 个空位，前三个不用计算，因为到第三个位置的Dp值和当前的Dp值一样。
Dp[]数组的下标变化大家可以参考循环队列的情况。
参考代码
/// 下面的是 minJump!=maxJump 时采用第一种方法压缩状态的。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_STONE 120
#define JUMP_MAX 20
int ngHead,ngHeadStart,ngMaxJump,ngMinJump,gDp[JUMP_MAX];
int myCmp(const int *a, const int *b){
if(*a > *b)
return 1;
else if(*a < *b)
return -1;
return 0;
}
void GetResult(int nJumpPoint){
int i,j,min,k,t[JUMP_MAX];
if(ngMinJump==ngMaxJump && ngHeadStart>nJumpPoint+ngMinJump)
ngHeadStart = nJumpPoint+(ngHeadStart-nJumpPoint-1)%ngMinJump+1;
for(i=ngHeadStart-1; i>=nJumpPoint; i--){
for(k=ngHead,j=i+1; j<i+ngMinJump;j++)
k = (k+1==ngMaxJump ? 0 : k+1);
for(min=gDp[k]; j<i+ngMaxJump; j++){
k = (k+1==ngMaxJump ? 0 : k+1);
min = gDp[k]<min ? gDp[k] : min;
}
ngHead = ngHead-1<0 ? ngMaxJump-1 : ngHead-1;
gDp[ngHead] = min;
memcpy(t,gDp,sizeof(int)*ngMaxJump);
qsort(t,ngMaxJump,sizeof(int),myCmp);
if(t[0]==t[ngMaxJump-1])
break;
}
ngHeadStart = nJumpPoint;
gDp[ngHead] = min+1;
}
int main(){
int nTest,nStones,i,j,k,s[MAX_STONE];
scanf("%d",&nTest);
for(i=0; i<nTest; i++){
scanf("%d",&k);
scanf("%d %d %d",&ngMinJump,&ngMaxJump,&nStones);
for(s[0]=0,j=1; j<=nStones; j++)
scanf("%d",&s[j]);
qsort(s,j,sizeof(int),myCmp);
for(ngHead=0,ngHeadStart=s[j-1],gDp[0]=k=1; k<ngMaxJump; k++)
gDp[k] = 0;
for(j-=2; j>=0; j--)
GetResult(s[j]);
printf("%d\n",gDp[ngHead]-1);
}
return 0;
}
/// 下面的是 minJump!=maxJump 时采用第二种方法压缩状态的。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_STONE 120
#define JUMP_MAX 20
int ngHead,ngHeadStart,ngMaxJump,ngMinJump,gDp[JUMP_MAX];
int myCmp(const int *a, const int *b){
if(*a > *b)
return 1;
else if(*a < *b)
return -1;
return 0;
}
void GetResult(int nJumpPoint){
int i,j,min,k;
if(ngMinJump==ngMaxJump && ngHeadStart>nJumpPoint+ngMinJump)
ngHeadStart = nJumpPoint+(ngHeadStart-nJumpPoint-1)%ngMinJump+1;
if(ngHeadStart > nJumpPoint+ngMaxJump*ngMaxJump){
for(min=gDp[0],i=1; i<ngMaxJump; i++)
min = gDp[i] < min ? gDp[i] : min;
for(i=0; i<ngMaxJump; i++)
gDp[i] = min;
}
else
for(i=ngHeadStart-1; i>=nJumpPoint; i--){
for(k=ngHead,j=i+1; j<i+ngMinJump;j++)
k = (k+1==ngMaxJump ? 0 : k+1);
for(min=gDp[k]; j<i+ngMaxJump; j++){
k = (k+1==ngMaxJump ? 0 : k+1);
min = gDp[k]<min ? gDp[k] : min;
}
ngHead = ngHead-1<0 ? ngMaxJump-1 : ngHead-1;
gDp[ngHead] = min;
}
ngHeadStart = nJumpPoint;
gDp[ngHead] = min+1;
}
int main(){
int nTest,nLength,nStones,i,j,k,s[MAX_STONE];
scanf("%d",&nTest);
for(i=0; i<nTest; i++){
scanf("%d",&nLength);
scanf("%d %d %d",&ngMinJump,&ngMaxJump,&nStones);
for(s[0]=0,j=1; j<=nStones; j++)
scanf("%d",&s[j]);
qsort(s,j,sizeof(int),myCmp);
for(ngHead=0,ngHeadStart=s[j-1],gDp[0]=k=1; k<ngMaxJump; k++)
gDp[k] = 0;
for(j-=2; j>=0; j--)
GetResult(s[j]);
printf("%d\n",gDp[ngHead]-1);
}
return 0;
}
本文系本站原创，转载请注明出处：http://xrkmonitor.com/a/dp_jump.html
very good !