本文共 4556 字，大约阅读时间需要 15 分钟。

题目

Description

假定给出一个包含N个整数的数组A，包含N+1个整数的数组ID，与整数R。其中ID数组中的整数均在区间[1,N-1]中。

用下面的算法对A进行Warshall-Turing-Fourier变换(WTF): sum = 0 for i = 1 to N index = min{ ID[i], ID[i+1] } sum = sum + A[index] 将数组A往右循环移动R位 将数组A内所有的数取相反数 for i = 1 to N index = max{ ID[i], ID[i+1] } index = index + 1 sum = sum + A[index] 将数组A往右循环移动R位 给出数组A以及整数R，但没有给出数组ID。在对数组A进行了WTF算法后，变量sum的可能出现的最大值数多少?

Input

第一行包含两个整数N与R。

第二行包含N个整数，代表A[1]到A[N]的值。

Output

第一行输出变量sum可能出现的最大值。

第二行输出此时的ID数组，包含N+1个整数。必须满足ID数组中每一个数均在区间[1,N-1]中。若有多个满足的ID数组，输出任意一组。 如果第一行是正确的（不管有没有输出第二行），你能得到该测试点50%的得分。

Sample Input

输入1：

5 3 1 -1 1 -1 1 输入2： 6 5 2 5 4 1 3 5

Sample Output

输出1：

10 1 1 1 2 2 3 输出2： 16 3 2 1 1 5 4 1

Data Constraint

对于20%的数据，N<=7。

对于60%的数据，N<=300。 对于100%的数据，2<=N<=3000, 1<=R<N, -10000<=A[i]<=10000。

题解

题意

有一种叫做WTF交换的东东（具体见题面）

现在给出数组$A$，$R$和$N$，求最大的$sum$和满足最大$sum$的$ID$数组（任意一种即可）

分析

DP

设$f[i][j]$表示$ID$数组的第$i$位选择$j$的最大$sum$

第一行

最初转移

枚举一个$k(1$~$n-1)$

$f[i][j]=max(f[i-1][k]+a[get(min(j,k))]-a[get(max(j,k)+1)])$ 何为$get$？ 若当前选择第$i$个位置 那么之前肯定进行过$i-1$次WTF操作 那么这个$j(k)$肯定会在数组内调换位置 $get$操作就是把一开始$j(k)$的位置找到 显而易见，这个转移是$O(n^3)$，只能拿60%的数据

优化

分类讨论：

当$k\le j$时： 原方程变为：$f[i][j]=max(f[i-1][k]+a[get(k)]-a[get(j+1)])$ 可以看出，$f[i-1][k]+a[get(k)]$是和$j$没有关系的 既然要让答案最大，那么$f[i-1][k]+a[get(k)]$就应该最大 那么就可以设一个$s$表示最大的$f[i-1][k]+a[get(k)]$ 至于怎么满足$k\le j$，就可以让$j$顺着扫一遍，那么最大的$s$所对应的$k$肯定是在$1$~$j$里的 手动模拟过程：

1. 新的$j$进入
2. 判断$f[i-1][j]+a[get(j)]$与$s$的大小，更新$s$
3. 判断$s-a[get(j+1)]$和$f[i][j]$的大小，更新$f[i][j]$

当$j\le k$时：

原方程变为：$f[i][j]=max(f[i-1][k]+a[get(j)]-a[get(k+1)])$ 可以看出，$f[i-1][k]-a[get(k+1)]$是和$j$没有关系的 既然要让答案最大，那么$f[i-1][k]-a[get(k+1)]$就应该最大 那么就可以设一个$s$表示最大的$f[i-1][k]-a[get(k+1)]$ 至于怎么满足$j\le k$，就可以让$j$倒着扫一遍，那么最大的$s$所对应的$k$肯定是在$j$~$n-1$里的 手动模拟过程：

1. 新的$j$进入
2. 判断$f[i-1][j]-a[get(j+1)]$与$s$的大小，更新$s$
3. 判断$s+a[get(j)]$和$f[i][j]$的大小，更新$f[i][j]$

原谅我偷懒

那么最大的$sum$就是最大的$f[n][i]$ 这时第一行求处理完了

第二行

处理第二行，其实就是要记每个$f[i][j]$是由哪个$k$转移过来的

开一个新的数组$g[i][j]$表示$ID$数组的第$i$位选择$j$的最大$sum$是从哪个$k$转移过来的 在上述的更新$f[i][j]$的那一步里顺便更新$g[i][j]$ 注意输出的时候，因为我们是由$g[1][]$转移到$g[2][]$转移到$g[3][]$……最后转移到$g[n][]$，所以要$dg$输出 先别急着去打 发现，这里的$g[i][j]$只有$n$个数 但题目要求的是$n+1$个数 那么第$n+1$个数是什么？？？ 其实就是最大$f[n][i]$的$i$

Code

#include
   
    #include
    
     #define inf 1234567890#define get(x) ((((x)-(i-1)*r)%n+n-1)%n+1)using namespace std;int n,r,i,j,s,ss,t,ans,a[3005],f[3005][3005],g[3005][3005];void dg(int x,int before){   	if (x!=0) dg(x-1,g[x][before]);	printf("%d ",before);}int main(){   	scanf("%d%d",&n,&r);	for (i=1;i<=n;i++)		scanf("%d",&a[i]);	for (i=1;i<=n;i++)	{   		ss=-inf;		for (j=1;j
     
      ss) 			{   				ss=s;				t=j;				}			if (ss-a[get(j+1)]>f[i][j])			{   				f[i][j]=ss-a[get(j+1)];				g[i][j]=t;			}		}		ss=-inf;		for (j=n-1;j>=1;j--)		{   			s=f[i-1][j]-a[get(j+1)];			if (s>ss) 			{   				ss=s;				t=j;				}			if (ss+a[get(j)]>f[i][j])			{   				f[i][j]=ss+a[get(j)];				g[i][j]=t;			}			}	}	ans=-inf;	for (i=1;i
      
       ans)		{   			ans=f[n][i];			t=i;		}	printf("%d\n",ans);	dg(n,t);	return 0;}