test20190416

Posted on | Edited on | Views:

来自 $GDOI​$ 的模拟题?

题面

$graph$

  • 貌似是第一次在考试中遇到提答题?
  • 这题看上去十分正常,却出成提答,就是让你乱搞的…题解给的做法就是退火之类的乱搞.
  • 随便估价乱搞一下就可以获得 $80+$ 的好成绩?

$guess$

  • 自己的联想发散能力还是有问题,没看出可以建网络流模型,只会打暴力…
  • 正解:要求的就是所有合法配对方案中,出现原来配对情况的最小数目.
  • 先离散化一下数字大小,建一个费用流的模型,从 $S$ 向左边每个数字连其在 $x$ 坐标中出现的次数作为流量, $0$ 作为费用的边. $y$ 坐标连类似的边连向 $T$ .中间对于每个原来有的配对,连一条流量为 $1$ ,费用为 $1$ 的边.这样就限制了不会出现重复的配对.
  • 跑一遍 $mcmf$ 即为答案.

$room$

  • 最开始想到最小割去了..然后发现好像不太现实,暴力转移的 $dp$ 倒是很普及…
  • 设 $f[i][j][k]$ 表示已经走了前 $i$ 层,第 $i$ 层开的门分别为 $j,k​$ 时的最小体力花费.
  • 这个东西显然可以 $O(nm^4)$ 大力转移.

$f[1][j][k]=t[1][j]+t[1][k]$
$f[i][j][k]=\min_{x\not = y} f[i-1][x][y]+K\cdot (|j-x|+|k-y|),2\leq i \leq n.​$

  • 后两维交换是没有影响的,所以在枚举是可以直接钦定 $j<k,x<y$ ,优化了 $16$ 倍常数.这样就有 $60pts$ 了.
  • $100pts?$ 转移时允许在同层转移,形成一个类似前缀 $\min$ 的优化,即可做到 $O(nm^2)$ . 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define rg register
using namespace std;
typedef long long ll;
const int inf=1e9;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=329;
int n,m,K;
int t[MAXN][MAXN];
int f[MAXN][MAXN][MAXN];
void solve()
{
	int ans=inf;
	memset(f,0x7f,sizeof f);
	for(rg int j=1;j<m;++j)
		for(rg int k=j+1;k<=m;++k)
				f[1][j][k]=t[1][j]+t[1][k];
	for(rg int i=2;i<=n;++i)
	{
		for(rg int j=1;j<m;++j)
			for(rg int k=j+1;k<=m;++k)
				f[i][j][k]=min(K+min(f[i][j-1][k],f[i][j][k-1]),f[i-1][j][k]);
		for(rg int j=m-1;j>=1;--j)
			for(int k=m;k>j;--k)
				f[i][j][k]=min(f[i][j][k],K+min(f[i][j+1][k],f[i][j][k+1]));
		for(rg int j=1;j<=m;++j)
			for(rg int k=j+1;k<=m;++k)
				f[i][j][k]+=t[i][j]+t[i][k];
	}
	for(rg int j=1;j<m;++j)
		for(rg int k=j+1;k<=m;++k)
			ans=min(ans,f[n][j][k]);
	cout<<ans<<endl;
}
int main()
{
	freopen("room.in","r",stdin);
	freopen("room.out","w",stdout);
	n=read(),m=read(),K=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			t[i][j]=read();
	solve();
	return 0;
}

可以滚掉第一维?空间没卡的话就随便吧…