过河 【状态压缩DP】+【完整的数论推导过程】

题目链接

  题意：很多人以为青蛙是要跳到石头上，一个个往后跳，问最少需要的石头数量，其实不然（题目给的样例的确也是有些坑了），青蛙每次都有跳的距离范围，题目求的是最少会跳到的石头，青蛙可以在水中起跳，它要尽可能的避开石头，也就是问抵达终点时最少需要必经的石头数。

思路：

  路很长，石头很少，很多次起跳绝对是在水里折腾，那么我们不如去优化这段在水里折腾的路径，反正在水里折腾的那部分时间不用计算到和里去。

• 如何路径压缩？

  在写上标准解之前，我先举这样的例子：假如S=4；T=5。那么到达哪一步的时候，青蛙能到达它之后的每一步？

  从0开始：0 4 5 8 9 10 12 13 14 15 16 17 18......发现一件事，从12开始，后面的每一步都可以由0开始经过一系列步伐之后得到，那么假如0～12这段间没有石头，我们就可以把石头距0所在的位置去%12 ，就能优化这段的路径。

  这是不是一个规律呢？或者存粹就是个偶然，不，我们可以距离其他数据，发现我们可以去“%((S-1)*(T-1))”去得到路径优化。那么，为什么会存在这样的一个规律，我们需要去找到其缘由：

  知道S与T，我们欲求得当它走到哪一步的时候，步步可走？（求极端值的想法，因为S与T差别越大，就说明其中点越多，越容易找到所求状态，所以我取S与T相邻情况）

第一次处理：S, T

第二次处理：2S, S+T, 2T

第三次处理：3S，2S+T，S+2T，3T

第四次处理：4S， 3S+T，2S+2T，S+3T，4T

......

第N次处理：NS，（N-1）S+T，......，S+（N-1）T，NT

我们需要处理到：N*T+1==（N+1）*S这样的一步，就说明链接上了，转移一下方程：(N+1)*S-N*T=1，将其中S与T看作是函数的两个变量，就得到了拓展欧几里得的这样的一个方程。又有gcd(N, N+1)恒等于1，故恒有两个大于零的解，即有解。那么，我们把S和T分别取到极限相邻值（9，10），就能发现，它们在第8次操作之后：72，73，74，75，......就是恒为所求状态，而所求模也就是(S-1)*(T-1)。但当S==1时，会使得S-1==0，故极限最长区间，我们令它为90（当然，80之类的也是可以，别取太小，毕竟还有极限值）。

• 状态转移方程：

  处理出要压缩的距离之后，我们知道每次需要压缩的距离，对于已经排序好的两两点，我们从前往后查询两两点之间的距离，如果它们的距离大于需要mod（90）的值，就将它们mod掉。

  处理完距离之后，就是状态转移方程，对应dp[i]=min(dp[i], dp[i-j]+live[i])，其中j的范围是[S, T]，live[i]指的是这个点是否有石头。

完整代码：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef long long ll;
const int maxN=9999;        //状压，拓欧可见规律在于T*(T-1)
int L, S, T, M;
int mp[110], dp[maxN<<2];      //mp[]记录原先距离原点的距离，dp[]记录到达这个点最小次数
bool live[maxN<<2];        //状压后判断这个点是否存在点？
bool cmp(int e1, int e2)
{
    return e1<e2;
}
int main()
{
    while(scanf("%d",&L)!=EOF)
    {
        mp[0]=0;        fill(dp, dp+maxN-1, maxN);      memset(live, false, sizeof(live));
        scanf("%d%d%d",&S,&T,&M);       int mod=80;
        for(int i=1; i<=M; i++) scanf("%d",&mp[i]);
        sort(mp+1, mp+1+M, cmp);  mp[M+1]=L;
        if(S==T)        //此时每次只能走固定点，需要独立考虑
        {
            int ans=0;
            for(int i=1; i<=M; i++) if(!(mp[i]%S)) ans++;       //能整除就说明这个点一定得走
            printf("%d\n", ans);
            continue;
        }
        for(int i=1; i<=M+1; i++)     //状压，包括要更改至end节点（没石头）
        {
            if(mp[i]-mp[i-1]>mod) mp[i]=mp[i-1]+(mp[i]-mp[i-1])%mod;
            live[mp[i]]=true;
        }
        dp[0]=0;
        for(int i=S; i<=T; i++) dp[i]=live[i];      //定义每个初始dp节点
        for(int i=2*S; i<=mp[M+1]; i++)
        {
            for(int j=S; j<=T && j<=i; j++)     //能抵达i点的点的最小石头利用次数
            {
                dp[i]=min(dp[i], dp[i-j]);
            }
            dp[i]+=live[i];
        }
        printf("%d\n", dp[mp[M+1]]-1);
    }
    return 0;
}