【2019.8.12 慈溪模拟赛 T1】钥匙（key）（暴力DP）

暴力\(DP\)

这题做法很多，有\(O(n^2)\)的，有\(O(n^2logn)\)的，还有徐教练的\(O(nlogn)\)的，甚至还有\(bzt\)的二分+线段树优化建图的费用流。

我懒了点，反正数据范围这么小，就写了个\(O(n^2)\)的暴力\(DP\)。

先将两个数组都排序，一个显然的性质，就是人选择钥匙时不可能相交。

所以我们设\(f_{i,j}\)表示前\(i\)个人选择了前\(j\)把钥匙时所用最大时间的最小值。

转移也很简单。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 1000

#define K 2000

#define INF 2e9

#define abs(x) ((x)<0?-(x):(x))

#define min(x,y) ((x)<(y)?(x):(y))

#define max(x,y) ((x)>(y)?(x):(y))

#define Gmin(x,y) (x>(y)&&(x=(y)))

using namespace std;

int n,m,p,a[N+5],b[K+5];

class DpSolver//暴力DP

{

	private:

		int f[N+5][K+5];

	public:

		I void Solve()

		{

			RI i,j,ans=INF;sort(a+1,a+n+1),sort(b+1,b+m+1);//排序

			for(i=1;i<=n;++i) for(j=0;j<=m;++j) f[i][j]=INF;//初始化

			for(i=1;i<=n;++i) for(j=i;j<=m;++j)//DP转移

				f[i][j]=min(max(f[i-1][j-1],abs(a[i]-b[j])+abs(p-b[j])),f[i][j-1]);

			printf("%d",f[n][m]);//输出答案

		}

}D;

int main()

{

	freopen("key.in","r",stdin),freopen("key.out","w",stdout);

	RI i;for(scanf("%d%d%d",&n,&m,&p),i=1;i<=n;++i) scanf("%d",a+i);

	for(i=1;i<=m;++i) scanf("%d",b+i);return D.Solve(),0;

}