《过河（P87）》题解
本题没有写数据范围。数据范围应是：1<=L<=100000，1<=N<=100，1<=M<=20000，1<=S<=T<=100。
本题一看就知道算法是DP，但如何确定状态？首先，本题需要一个至少二维的状态，因为位置、所放的石子个数和步数这三个量中至少需要两个作为状态，另一个作为结果。但是，位置（L）的上限为100000，石子数（M）的上限为20000，而步数，由于L较大而S、T较小，其上限也是很大的。这样，看起来任意两个量作为状态，其上限的乘积都会超过10^8，这样肯定会MLE了。
由于L的上限为100000，而N的上限为100，可见原有的石子分布地相当稀疏，两个石子中间的空当很大。这样，能不能只用原有的石子来表示位置？这样，位置的上限就减为100，不管第二维是另外两个量中的哪个，都不会MLE了。但是，这样的话状态转移就变得很麻烦。
首先要做一个预处理：设G[i]为走过一段长度为i的空当，至少需要放上几个石子。也就是起点为0终点为i，中间一个原有的石子也没有，问至少要放几个石子才能从0走到i？
边界：G[0] = 0
i>0时，G[i] = min(G[i-j])+1 (s<=j<=t且i>j)
然后，确定本题的状态：F[i][j]表示走到原有的第i个石子处（刚好站在第i个石子上面），且在第i个石子之前额外放上j个石子的最少步数。以下设A[i]为第i个石子的位置，并虚设“第0个石子”为起点0（A[0]=0）。
枚举上一个到达的原有石子，设为第k个（也就是，对于第(k+1)个到第(i-1)个原有石子，都不理它们，就当它们不存在），则A[k]~A[i]中间的那一段相当于空当。
则F[i][j] = min(F[k][j-G[A[i]-A[k]]+1] + G[A[i]-A[k]])（满足0<=k<i，G[A[i]-A[k]]-1<=j）
边界：F[0][0]=0，当j>0时，F[0][j] = ∞。
然后，本题要求过河所用的最少步数。求完F数组后，枚举最后一个到达的原有石子i（A[i]以后相当于空当），并设在A[i]之前额外放上j个石子。设k为过河前最后一个到达的位置（这里额外放上石子），k应在(L-T+1)~L范围内（这样再一步就可以过河了）。可得结果为min(F[i][j] + G[k-A[i]]) + 1（满足L-T+1<=k<=L且K>=A[i]，j+G[k-A[i]]<=M）
如果最后求出的结果为∞，则无法过河，此时要求出最远能到达哪里。求法：仍然枚举最后一个到达的原有石子i和在A[i]之前额外放的石子个数j。若F[i][j]为∞，则跳过，否则求出A[i] + (m - j) * t的值，取最大的即为结果。
复杂度分析：时间复杂度O(N^2*M)，空间复杂度O(NM)。