GMOJ 1281旅行 题解

warning:此方法可能较难理解 讲的烂

约定

1. 除去标有“移动”，所有的 \(A\) 都为原始输入顺序。

2. \(i\text{~}j\) 的“代价”定义为 \(\sum_{i}^{j}|A_i-A_j|\) .

思路

这种题比较明显的是DP，有两种解法。我果然选择了空间更差不能优化的顺推法

首先，由于交换的位置从前往后，所以一个数要么向前移动1位，要么向后移动若干位（包括0）

用不加调料的脑回路设状态：

假设 \(A_i\) 向后移动，那么 \(A_{i-1}\) 与 \(A_{i}\) 肯定没有交换。明显的，对于 \(i\) 固定的情况下，能转移的前置 \(F\) 一定是固定的，为 \(F_{k,i-1}\phantom{1}(k<i)\) 。同时，因为第 \(i-1\) 个数（\(A_k\)）和第 \(i\) 个数（注意是 \(A_{i+1}\)，\(A_i\) 被换出去了）是确定的，所以移动后 \(1\text{~}i\) 的代价是固定的，可以以 \(O(N)\) 的时间复杂度计算。

然后，对于移动后 \(i\text{~}j\) 的代价，因为只有 \(A_i\) 在移动，所以 \(A_{i+1}\text{~}A_j\) 的相对位置是不变的，于是移动后 \(i+1\text{~}j\) 的代价当然也是不变的，可以预先用一个 \(S\) 数组 \(O(n^2)\) 预处理每个区间的代价。在此基础上，再加上 \(|A_i-A_j|\) ，就是移动后 \(i\text{~}j\) 的代价。

那么，我们可以列出一条式子：

（\(S_{i,j}\) 表示原来中 \(i\text{~} j\)的代价）

对于 \(min\) 函数内的部分，就是之前提到可以预处理的部分。

我们要注意到这条式子有一个限制条件：\((i<j)\) ，因为我们假定 \(A_i\) 移动。

对于不移动的情况，我们只需要考虑前置 \(F\) 和结尾与 \(A_i\) 的差即可：

(注意 \(min\) 函数里面的差别)

那么，最后的答案就是枚举一下谁在最后，即：

实现

注意对于 \(i=1\) 时，\(F_{i,i}\) 和 \(min{\{F_{k,i-1}+|A_{i+1}-A_k|\}}\) 的值为0，由于不会被转移，需要特殊处理。

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,ans=0x7fffffff,a[2010],s[2010][2010],f[2010][2010];
void read(int &x){
	char c=getchar();
	for(;c<33;c=getchar());
	for(x=0;(c>47)&&(c<58);x=x*10+c-48,c=getchar());
}
int main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			s[i][j]=s[i][j-1]+abs(a[j]-a[j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		int temp=f[i][i]=i==1?0:0x7fffffff;
		for(int j=1;j<i;j++){
			temp=min(temp,f[j][i-1]+abs(a[i+1]-a[j]));
			f[i][i]=min(f[i][i],f[j][i-1]+abs(a[i]-a[j]));
		}
		for(int j=i+1;j<=n;j++){
			f[i][j]=temp+abs(a[i]-a[j])+s[i+1][j];
		}
	}
	for(int i=1;i<=n;i++){
		ans=min(ans,f[i][n]);
	}
	printf("%d",ans);
}

GMOJ 1281旅行 题解

原文：https://www.cnblogs.com/groundwater/p/13308211.html