题意:给你n个牛牛,n<=12,每一个牛有三个朋友,他必须和他的伙伴连一条线(线的权值为他俩之间的距离),问怎样排序母牛使得总权值和最小。
思路: 首先n=12,所以全排列的话数虽然不大但也不小,正解给了个装压dp我不会,但随机数了一波直接过了。就是我们随机一个序列,初始化为1.到n,然后每次更换其中的两个数使得序列发生变化,然后跑1e6次就可以了。
Farmer John's N cows (4 <= N <= 12, N even) have built a primitive system for communicating between pairs of friendly cows by building wires protected by wrappings made of hay.
Each cow has exactly 3 other friends in the barn, and the cows must arrange themselves to occupy N stalls lined up in a row. A wire of length L requires exactly L units of hay to build, so for example if the cows in stalls 4 and 7 are friends, it would take 3 units of hay to construct a wire to connect them.
Assuming every pair of friends must be connected by a separate wire, please determine the minimum possible amount of hay required to build these wires if the cows order themselves in the best possible way.
输入
* Line 1: The integer N. FJ's cows are conveniently numbered 1..N.
* Lines 2..1+N: Each line contains three space-separated integers in the range 1..N. Line i+1 contains the numeric identifiers of the three friends of cow i. If cow i is a friend of cow j, then j will also be a friend of i.
输出
* Line 1: The minimum total amount of hay required to connect all pairs of friendly cows.
样例输入 Copy
1
2
3
4
5
6
76 6 2 5 1 3 4 4 2 6 5 3 2 4 6 1 1 5 3
样例输出 Copy
117
提示
There are 6 cows. Cow 1 is friends with cows 6, 2, and 5, etc.A best ordering of the cows is 6, 5, 1, 4, 2, 3, which requires only 17 units of hay.
[提交][状态]
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#include<bits/stdc++.h> using namespace std; const int maxx=1e5+12; #define ll long long const ll mod=1000000007; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n; ll pos[13]; int dp[13][13]={0}; const ll inf=1e18+4; int bian[13][13]={0}; int a[13]={0}; ll f() { ll ans=0; for(int i=1;i<=n;i++) pos[a[i]]=i; for(int i=1;i<=n;i++) { for(int j=1;j<=3;j++) { ans+=abs(pos[dp[a[i]][j]]-i); } } return ans; } int main() { ll i,j,k,m,s,x,y,t,l,r; ll sum=0; cin>>n; for(i=1;i<=n;i++) { for(j=1;j<=3;j++) { dp[i][j]=read(); } } if(n==4) { printf("10n"); return 0; } for(i=1;i<=n;i++) { a[i]=i; } int cishu=1; ll minl=100000000000; while(cishu<=1000000) { //for(i=1;i<=n;i++) printf("%d ",a[i]); //printf("n"); //printf("%lldn",f()); l=rand()%n+1; r=rand()%n+1; swap(a[l],a[r]); minl=min(minl,f()); cishu++; } printf("%lldn",minl/2); return 0; }
最后
以上就是迷路犀牛最近收集整理的关于Haywire (随机数大法好)的全部内容,更多相关Haywire内容请搜索靠谱客的其他文章。
发表评论 取消回复