L · Loop：中文题面与个人代码

时限 1 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

给定长度为 $n$ 的非负整数序列 $a_0,\ldots,a_{n-1}$ ，构造 $n\times n$ 方格。第零列自上而下为原序列，此后每一列都是前一列向下循环移动一格。因此第 $i$ 行、第 $j$ 列的权值为 $a_{(i-j)\bmod n}$ 。

从左上角 $(0,0)$ 出发，每步只能向右或向下，走到右下角 $(n-1,n-1)$ 。路径上每一个经过的格子都计入，包括起点和终点。求最小权值和。

输入、输出与约束 #

$1\le T\le10^3$ 。每组输入 $1\le n\le10^5$ ，随后输入 $n$ 个 $0\le a_i\le10^9$ 。保证所有组的 $\sum n\le10^5$ 。每组输出一个整数。路径共有 $2n-1$ 个格子，必须使用能容纳约 $2\times10^{14}$ 的整数类型。

样例 #

输入 1 #

7
4
3 4 2 1
1
7
5
8 0 9 0 1
7
5 1 9 0 0 9 9
4
1 1000 1000 1
6
4 0 9 0 1 9
3
1000000000 1000000000 1000000000

输出 1 #

样例说明 #

第一组一条最优路径经过的权值为 $3,1,2,1,2,1,3$ ，和为 $13$ 。 $n=1$ 时只计唯一格子，答案 $7$ 。最后一组所有格子均为 $10^9$ ，路径有五格，所以答案是 $5\times10^9$ ，超过有符号 32 位整数。

个人代码：把方格路径压成一维往返 #

令 $d=i-j$ 。向下走令 $d$ 加一，向右走令 $d$ 减一，当前权值只由 $d\bmod n$ 决定。整个过程是一条从零出发又回到零、长为 $2(n-1)$ 的一维步行。这样的闭合步行恰有 $n-1$ 次加一、 $n-1$ 次减一，任意前缀也不会超过最终次数，因此能够还原成合法方格路径。

对一维整数线上的边 $\{d,d+1\}$ ，向两个方向的通过次数相等，记各为 $t_d$ 。路径代价可写成“起点权值加每次往返的代价”：

$a_0+\sum_d t_d\bigl(a_{d\bmod n}+a_{(d+1)\bmod n}\bigr),\qquad\sum_dt_d=n-1.$

在任意可行步行经过的边中选往返代价最小的一条。保留从零到它所需的各边一次往返，把其余往返都集中到这条最便宜的边，代价不会增大。于是存在一个最优解：先向某一方向到达一条边，在那条边上反复往返，再回到零。枚举这条边与到达方向即可。

对照一基下标的公式 #

代码中 a[1] 对应题面的 $a_0$ ，sum[i] 是前缀和。向正方向到达 a[i] 与 a[i+1] 之间，前面的 $i-1$ 条边各往返一次，目标边往返 $n-i$ 次，得到

$2\operatorname{sum}[i-1]+a[i]+(n-i)(a[i]+a[i+1]).$

反方向到达同一相邻对时，先经过 a[1],a[n],...,a[i+1]，得到

$2(\operatorname{sum}[n]-\operatorname{sum}[i+1]+a[1])+a[i+1]+(i-1)(a[i]+a[i+1]).$

反向公式在 $i=1$ 时目标边往返次数为零，代码不枚举它；对应的极端单调往返路线不会优于它经过的某条可重复边，已由其他候选覆盖。跨接 a[1] 与 a[n] 的边单独给出候选 $(a[1]+a[n])(n-1)+a[1]$ 。 $n=1$ 时循环为空，最后这个公式自然返回唯一格子的权值。

时间 $O(n)$ ，前缀和空间 $O(n)$ 。最大答案不超过 $(2n-1)10^9$ ，原稿用 long long 足够。

本地结果： 样例通过；923 组数组与独立的 $O(n^2)$ 方格最短路 DP 一致，其中长度不超过五、元素取 $0,1,2$ 的数组全部枚举，并补充更长随机数组。 $n=10^5$ 且元素全为 $10^9$ 时输出 $199999000000000$ ，符合路径格子数。

原始 C++ 文件 #

下载 L.cpp · 验证说明

下面展示原稿，保留未完成部分和已发现问题；下载文件保留原始字节。SHA-256：404409239ef1a35e6e2a9296d5d31636f995b7f67e5efca903f42a593c129a81。

#include<bits/stdc++.h>
#define int long long
const int inf=1e18;
using namespace std;
int read(){
	int x;scanf("%lld",&x);
	return x;
}
int n,a[100005],sum[100005];
void solve(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),sum[i]=sum[i-1]+a[i];
	int ans=inf;
	for(int i=1;i<n;i++){
		int cnt=n-1-(i-1);
		ans=min(ans,(a[i]+a[i+1])*cnt+sum[i-1]*2+a[i]);
		if(i!=1){
			cnt=n-1-(n-i);
			ans=min(ans,(a[i]+a[i+1])*cnt+(sum[n]-sum[i+1]+a[1])*2+a[i+1]);
		}
//		cout<<i<<" "<<ans<<" "<<cnt<<endl;
	}
	ans=min(ans,(a[1]+a[n])*(n-1)+a[1]);
	printf("%lld\n",ans);
}
signed main(){
	int t=read();
	while(t--)solve();
}