一眼无脑 dp，直接看当前 $j$ 跟上一个 $j$ 的大小关系。

发现时间复杂度是 $O(N^3)$，考虑直接暴力旋转然后前缀最大值后缀最小值优化。

然后你就发现第一行算好了。

至于构造直接开 pre 数组在前缀最大值时记录一下哪个点最大直接 pre 过去即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3010;
int dp[N][N],a[N],b[N],mx[N],mn[N],id[N],id1[N],pre[N][N];
signed main()
{
	int n,m;cin>>n>>m;mx[0]=-1e9;mn[n+1]=1e9;
	for(int i=1;i<=n;i++)cin>>a[i];
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<n;i++)dp[0][i]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			mx[j]=mx[j-1];id[j]=id[j-1];
			int t=dp[i-1][j]+a[j];
			if(t>mx[j])mx[j]=t,id[j]=j;
		}
		for(int j=n;j>=1;j--)
		{
			mn[j]=mn[j+1],id1[j]=id1[j+1];
			int t=a[j]-dp[i-1][j-1];
			if(t<mn[j])mn[j]=t,id1[j]=j;
		}
		for(int j=1;j<n;j++)
		{
			dp[i][j]=mx[j]-a[j+1];pre[i][j]=id[j];
			int t=a[j]-mn[j+1];
			if(t>dp[i][j])dp[i][j]=t,pre[i][j]=id1[j]-1;
		}
		for(int j=1;j<=n;j++)
		{
			int npos=j-m;
			if(npos<=0)npos+=n;
			b[j]=a[npos];
		}
		for(int j=1;j<=n;j++)a[j]=b[j];
	}
	int ans=-1e9,iid=0;for(int i=1;i<n;i++)if(dp[n][i]>ans)ans=dp[n][i],iid=i;
	deque<int>q;
	for(int i=n,x=iid;i>=0;i--)q.push_front(x),x=pre[i][x];
	cout<<ans<<'\n';
	for(int y:q)cout<<y<<' ';
	return 0;
}

题目大意

翻译的基本题面就不多说了，我们来大概分析一下题目。

• 序列会变回来：我们可以观察到，在 $n$ 次变换后，序列会还原。也就是说，两个循环在同一个 $i$ 上操作的序列是一样的。
• 下标的空间：然后我们再分析一下不难发现，下标是一大一小，也就是 $\min\left(ID_{i},ID_{i+1}\right)$ 和 $\min\left(ID_{i},ID_{i+1}\right)+1$，所以我们求 $ID_i$ 时，去求 $ID_{i-1}$ 就好了。聪明的小朋友想到动态规划了，那么再找找。
• 连续性：再找一找就可以发现就是选择一些边，那么就可以知道状态之间是关联的。

思路概述

经过了上面的思考，我们就不难可以发现，这道题肯定用动态规划。我总结了两种方法供大家食用：

强行 dp

这种思路是我一开始想出来的，其实挺好设的。我们就设 $f_{i,j}$ 表示在 $i$ 的时候选 $j$ 所能取到的最大贡献，所以我们就可以得到一个转移方程。

$$f_{i,j}=\max_{k=1}^{n-1}\left(f_{i-1,k}+A_{\min\left(j,k\right)}-A_{\max\left(j,k\right)}+1\right)$$

但是肯定有同学一眼丁真，发现时间复杂度太大了，所以我们优化成这个样子：

$$f_{i,j}=\max\left(A_j+\max_{k=j}^{n-1}\left(f_{i-1,k}-A_{k+1}\right)-A_{j+1}+\max_{k=1}^{j}\left(f_{i-1,k}+A_{k}\right)\right)$$

然后后面的东西我们可以使用前缀或者是后缀和搞定。然后我们上一下核心代码：

pre[0]=suf[n]=-1e9;
for(i=1;i<=n;++i,solve()){
   for(k=1;k<n;++k){
   	if(pre[k-1]>=f[i-1][k]+A[k]){
   		pre[k]=pre[k-1];
   		pref[k]=pref[k-1];
   	}else{
   		pre[k]=f[i-1][k]+A[k];
   		pref[k]=k;
   	}
   }
   for(k=n-1;k;--k){
   	if(suf[k+1]>=f[i-1][k]-A[k+1]){
   		suf[k]=suf[k+1];
   		suff[k]=suff[k+1];
   	}else{
   		suf[k]=f[i-1][k]-A[k+1];
   		suff[k]=k;
   	}
   }
   for(j=1;j<n;++j){
   	int p=pre[j]-A[j+1],s=suf[j]+A[j];
   	if(p>=s){
   		f[i][j]=p;
   		trans[i][j]=pref[j];
   	}else{
   		f[i][j]=s;
   		trans[i][j]=suff[j];
   	}
   }
}

但是，这个空间复杂度不够优秀，所以我们再换一种。

正解

那么我们可以对于每一个 $i$ ，我们可以设

$$id_1=\min(ID_i,ID_{i+1}),id2=min(ID_i,ID_{i+1})$$

所以，我们就可以得到 $sum=A_{id_i}-A_{id_2+1}$。 同时，这也让我们想到了差分这件事情，所以我们可以构建出一个 $\left(n-1\right)\times n$ 的矩阵，每一行都是旋转后记录的差分数组。但是动态规划的数组怎么设计呢？其实很简单，设 $f_{i,j,k}$ 表示走到了 $\left(i,j\right)$ 这个位置的时候，方向是 $k$ 的最长路径，所以就有如下的转移方程。

$$f_{i,j,0}=\max\left(f_{i-1,j,0/1/2}+B_{i,j}\right) f_{i,j,1}=\max\left(f_{i,j+1,0/1}+B_{i,j}\right) f_{i,j,2}=\max\left(f_{i,j-1,0/2}+B_{i,j}\right)$$

代码就不贴了。