明显能够看出有一个建图求路程的优化 然而发现10000*10000爆空间QAQ
为了做一些初始化方面的优化 我们发现了一个叫做前缀和的东西 可以在环上查到两个之间的最短距离
同时还要做一些查询代价方面的优化 比如由在城市1建厂推出在其它城市建厂的代价
（然而由于本人过于蒟蒻 所以不会）
那么还有一种方法
其实本题难点就在于环上怎样查询代价
我们有这样一个方法
把环展成两部分 在下标分别为i以及i+n的两个位置之间找到待查找的值并找最小值
这样思路就很明显了
上代码
#include <iostream> #include <cstdio> #include <climits> using namespace std; const int M=10005; int n,m,dis,a,b; long long c; int d[M],z[M]; long long sum[M]; long long ans=LLONG_MAX; int main() { freopen("bro.in","r",stdin); freopen("bro.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) { scanf("%d%d",&z[i],&d[i]); sum[i]=sum[i-1]+d[i]; } for(int i=1;i<=n;i++) { long long tot=0; for(int j=1;j<=n;j++) { a=max(i,j),b=min(i,j),c=sum[a]-sum[b-1]-d[a];//前缀和 dis=min(c,sum[n]-c);//破环成链 tot+=dis*z[j]; } ans=min(ans,tot); } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/qxds/p/9821533.html