bzoj 4670 佛罗里达

Posted on | Edited on | Views:

随机乱搞.

  • 随机做很多次,每次 $random\ shuffle$ 出一个加点的序列,然后按照这个序列加点.
  • 每次贪心判,加在哪个集合里面能使答案增加的量更小,就加在哪个里面.
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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 T=800;
const int inf=0x7fffffff;
const int MAXN=256;
int n,val[MAXN][MAXN],p[MAXN];
int A[MAXN],sizA,B[MAXN],sizB,mxA,mxB;
ll ans;
int main()
{
	srand(time(NULL));
	while(~scanf("%d",&n))
	{
		ans=inf;
		memset(val,0,sizeof val);
		for(int i=1;i<n;++i)
			for(int j=i+1;j<=n;++j)
				val[i][j]=val[j][i]=read();
		for(int i=1;i<=n;++i)
			p[i]=i;
		for(int t=1;t<=T;++t)
		{
			ll res=0;
			random_shuffle(p+1,p+1+n);
			sizA=sizB=0;
			mxA=mxB=0;
			for(int i=1;i<=n;++i)
			{
				int valA=0,valB=0;
				for(int j=1;j<=sizA;++j)
					valA=max(valA,val[p[i]][A[j]]);
				for(int j=1;j<=sizB;++j)
					valB=max(valB,val[p[i]][B[j]]);
				if(valA<=mxA && valB<=mxB)
				{
					int k=rand()&1;
					if(k)
						A[++sizA]=p[i];
					else
						B[++sizB]=p[i];
					continue;
				}
				if(valA-mxA<=valB-mxB)
				{
					if(valA-mxA>0)
					{
						res+=valA-mxA;
						mxA=valA;
					}	
					A[++sizA]=p[i];
				}
				else
				{
					if(valB-mxB>0)
					{
						res+=valB-mxB;
						mxB=valB;
					}	
					B[++sizB]=p[i];
				}
				if(res>=ans)
					break;
			}
			ans=min(ans,res);
		}
		cout<<ans<<endl;
	}
	return 0;
}