洛谷P2662 牛场围栏

首先随便找一种长度的围栏，比如$p$
设$d\left [ r \right ]\equiv r\left ( mod \ p \right )$，且为最小的不能修建的长度
根据定义，$d\left [ r \right ]+t*p\left ( t \in \mathbb{N} \right )$均能修建，$d\left [ r \right ]+t*p\left ( t < 0\right )$均不能修建

求$d$的过程就是求最短路
首先$d\left [ 0 \right ]=0$，其次可用$d\left [ x \right ]+a_{i}$更新$d\left [ \left ( x+a_{i} \right ) mod \ p\right ]$
显然$p$越小，复杂度越低

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int N=3050,INF=1<<30;
int n,m,d[N],inq[N],mod,ans;
vector<int> w;
queue<int> Q;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void SPFA()
{
    for(int i=0;i<mod;i++) d[i]=INF;
    d[0]=0,inq[0]=1,Q.push(0);
    while (!Q.empty())
    {
        int x=Q.front();
        Q.pop(),inq[x]=0;
        for(int i=0;i<w.size();i++)
            if (d[x]+w[i]<d[(x+w[i])%mod])
            {
                d[(x+w[i])%mod]=d[x]+w[i];
                if (!inq[(x+w[i])%mod])
                {
                    inq[(x+w[i])%mod]=1;
                    Q.push((x+w[i])%mod);
                }
            }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        int x=read();
        for(int k=x;k>=max(1,x-m);k--) w.push_back(k);
    }
    sort(w.begin(),w.end());
    w.resize(unique(w.begin(),w.end())-w.begin());
    if ((mod=w[0])==1)
    {
        puts("-1");
        return 0;
    }
    SPFA();
    for(int i=0;i<mod;i++)
        if (d[i]==INF)
        {
            puts("-1");
            return 0;
        }
    for(int i=0;i<mod;i++)
        ans=max(ans,d[i]);
    printf("%d\n",ans-mod);
    return 0;
}