题解：P13404 [GCJ 2010 #3] Fence
__EternalLife__
·
·
题解
同余最短路好困难！
首先，令 mx=\max_{1\le i\le N} B_i，则任意一种合法方案都可以表示为先用一些长度小于 mx 的木板拼出一个长度 S，剩下的长度 L-S 全部用长度为 M 的补齐。
:::warning[错误想法]
可能有些人会把上面理解为贪心，即尽可能用最长的拼，但这是错误的！我们上述的其实是对于每一种合法的方案，而并非最优方案。
:::
所以 L=q\times mx+r。
答案即为
c+\frac{L-S}{mx}=\frac{L+cmx-S}{mx}
其中 c 表示组成长度为 S 的木板数。
为了使得方案合法，即恰好拼出所需长度，我们需要使得 $S\equiv r\pmod{mx}$，所以我们只用关心 $S$ 模 $mx$ 后的余数，而并非 $S$ 本身。容易想到同余最短路。
所以我们在模 $mx$ 意义下建图即可，具体的，对于 $u\in [0,A-1]$，连从 $u$ 到 $(u+b_i)\bmod mx$ 的边，那么边权即为选择 $b_i$ 产生的代价，那么这个代价是多少呢？
因为 $cmx-S=\sum_{i=1}^c mx-b_i$，所以选择 $b_i$ 的代价即为 $mx-b_i$。
综上，我们连从 $u$ 到 $(u+b_i)\bmod mx$ 的边，边权为 $mx-b_i$，然后以 $0$ 为源点跑最短路，得到 $dis_r$。$dis_r$ 即表示 $cmx-S=\sum_{i=1}^cmx-b_i$ 的最小值。
那么最后输出 $\frac{L+dis_r}{mx}$ 即可。
:::success[Code]
```
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
long long L;
int n;
int b[maxn];
struct node{
int to,next;
long long w;
}e[10000000+5];
int head[maxn],tot;
void add(int u,int v,long long w){
e[++tot].to=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot;
}
struct qnode{
int u;
long long w;
qnode(int uu,long long ww){u=uu;w=ww;}
friend bool operator<(qnode q1,qnode q2){
return q1.w>q2.w;
}
};
bitset<maxn> vis;
long long dis[maxn];
void dij(int s){
memset(dis,0x3f,sizeof(dis));
vis.reset();
priority_queue<qnode> pq;
dis[s]=0; pq.push({s,0});
while(!pq.empty()){
qnode top=pq.top(); pq.pop();
if(vis[top.u]) continue;
vis[top.u]=1;
for(int i=head[top.u];i;i=e[i].next){
int v=e[i].to;
if(dis[v]>dis[top.u]+e[i].w){
dis[v]=dis[top.u]+e[i].w;
pq.push({v,dis[v]});
}
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T,cnt=1;
cin>>T;
while(T--){
cout<<"Case #"<<cnt<<": "; cnt++;
memset(head,0,sizeof(head)); tot=0;
cin>>L>>n;
int A=0;
for(int i=1;i<=n;i++) cin>>b[i],A=max(A,b[i]);
int r=L%A;
for(int u=0;u<A;u++){
for(int i=1;i<=n;i++){
int v=(u+b[i])%A;
add(u,v,A-b[i]);
}
}
dij(0);
if(dis[r]==0x3f3f3f3f3f3f3f3f){
cout<<"IMPOSSIBLE"<<endl; continue;
}
cout<<(long long)(L+dis[r])/A<<endl;
}
return 0;
}
```
:::
真的好困难！