状态压缩类问题：过河

【问题简述】一个独木桥，可看做一个数轴，上面每个点的坐标分别为0、1、2、……、L（L≤109）。青蛙

从坐标为0的点出发，不停地跳跃，直到跳到或超过 L 点。它一次跳跃的距离最小为 S，最大为 T（包括 S、T，

1≤S≤T≤10）。

独木桥上有 M（M≤100）个石子，位置都是已知的，并且不会重叠。青蛙讨厌踩到石子上。问：青蛙若想通过独木桥，最少要踩几个石子？

【分析】很容易想出，若 f(i)表示从起点到达 i 坐标点所踩到石子的最小个数，则 f(i)=min{f(i－k)}＋f(i)，s≤k≤t 但是，我们无法开长度为1000000000的数组，即使能开，程序也不可能在1s内结束。

仔细观察数据规模，就会发现，石子的数量非常稀少！所以，长长的空隙一定可以被压短。

以下代码首先对stone进行了排序，然后令L=stone-stone[i-1]。当L%t==0时，令k=t；当

L%t!=0时，令k=L%t。然后令k为k+t。

最后判断如果k>L，那么map[]数组中stone和stone[i-1]两石头的距离就被等效成为L；如果

k<=L，那么map[]数组中stone和stone[i-1]两石头的距离就被等效成为k。

接下来就可以用动态规划了。

#include <iostream> #include <cstring> #include <algorithm> using namespace std; int stone[101], map[100001], f[100001]; int s,t,m,p=0,q; int main() {  int l,k,result;  memset(stone,0,sizeof(stone));  memset(map,0,sizeof(map));  memset(f,0,sizeof(f));    cin>>l>>s>>t>>m;  for(int i=1;i<=m;i++) cin>>stone;    // 读入石子坐标  sort(stone+1,stone+m+1);    for(int i=1;i<=m;i++)        // 缩短数组，p为map[]长度 {   l=stone-stone[i-1];   if(l%t==0) k=t; else k=l%t;   k+=t;   if(l<k) k=l;   p+=k;   map[p]=1; }    for(int i=1;i<=p+t;i++)        // 动态规划 {        result=200;   for(int j=i-t;j<=i-s;j++)    if(j>=0 && f[j]<result) result=f[j];   f=result+map; } result=200;  for(int i=p+1;i<=p+t;i++) if (f<result) result=f; // 找最小值  cout<<result;  return 0; }