洛谷 P2662 牛场围栏

做法是这样的：

首先暴力把所有可能的边长搞出来。。（当然<=0的不要）

排序边长+去重，

当且仅当可行边长里面有1时，任何长度都能取到，输出-1

当且仅当所有可行边长的gcd大于1时，不能取到的长度没有上限，输出-1

其他情况，一定有解；设最短的可行边长为x

将所有可行边长按除以x的余数分类，一类建立一个点（除以x的余数为u，则建立u点）

对于每一个可行边长y，对于每一个点u，从点u向点(u+y)%x连一条长度为y的边

可以发现从0号点向任意点u的最短路长度(dijkstra跑出来)（设为d），就是所有能取到的总长度中，除以x的余数为u的之中，最短的；且这一类（指除以x的余数为u的长度）中，所有大于d的长度也都能取到（只要加上一些长度为x的边就行了）；因此，d-x就不能取到了

那么最大的不能取到的就是所有“d-x”的最大值（等于“所有d的最大值”-x）

严谨一些的证明要比noip那道复杂很多啊。。根本不会，以后再说吧

https://blog.csdn.net/Timsei/article/details/63254318

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<queue>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int n,m;

 int tt[];

 priority_queue<pii,vector<pii>,greater<pii> > q;

 int d[],mm=-0x3f3f3f3f;

 bool vis[];

 int main()

 {

     int i,j,u,v;pii t;

     scanf("%d%d",&n,&m);

     for(i=;i<=n;i++)

     {

         scanf("%d",&u);

         for(j=;j<=m;j++)

         {

             if(u-j<=)    break;

             tt[++tt[]]=u-j;

         }

     }

     sort(tt+,tt+tt[]+);tt[]=unique(tt+,tt+tt[]+)-tt-;

     if(tt[]==)

     {

         puts("-1");

         return ;

     }

     int g=tt[];

     for(i=;i<=tt[];i++)    g=__gcd(g,tt[i]);

     if(g!=)

     {

         puts("-1");

         return ;

     }

     memset(d,0x3f,sizeof(d));

     q.push(mp(,));d[]=;

     while(!q.empty())

     {

         t=q.top();q.pop();

         u=t.se;

         if(vis[u])    continue;

         vis[u]=;

         for(i=;i<=tt[];i++)

         {

             v=(u+tt[i])%tt[];

             //printf("%d %d\n",u,v);

             if(d[v]>d[u]+tt[i])

             {

                 d[v]=d[u]+tt[i];

                 q.push(mp(d[v],v));

             }

         }

     }

     for(i=;i<tt[];i++)    mm=max(mm,d[i]);

     printf("%d",mm-tt[]);

     //for(i=0;i<tt[1];i++)    printf("%d %d\n",i,d[i]);

     return ;

 }