首页 > 代码库 > bzoj4745: [Usaco2016 Dec]Cow Checklist

bzoj4745: [Usaco2016 Dec]Cow Checklist

2024-08-29 21:59:12   217人阅读

bzoj4745: [Usaco2016 Dec]Cow Checklist

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Discuss]

Description

Every day, Farmer John walks through his pasture to check on the well-being of each of his cows. Onh
is farm he has two breeds of cows, Holsteins and Guernseys. His HH Holsteins are conveniently number
ed 1…H, and his GG Guernseys are conveniently numbered 1…G (1≤H≤1000,1≤G≤1000). Each cowis loc
ated at a point in the 2D plane (not necessarily distinct).Farmer John starts his tour at Holstein 1
, and ends at Holstein HH. He wants to visit each cow along the way, and for convenience in maintain
ing his checklist of cows visited so far, he wants to visit the Holsteins and Guernseys in theorder 
in which they are numbered. In the sequence of all H+GH+G cows he visits, the Holsteins numbered 1…
H should appear as a (not necessarily contiguous) subsequence, and likewise for the Guernseys. Other
wise stated, the sequence of all H+GH+G cows should be formed by interleaving the list of Holsteins 
numbered 1…H with the list of Guernseys numbered 1…GWhen FJ moves from one cow to another cow trav
eling a distance of D, he expends D2 energy. Please help him determine the minimum amount ofenergy r
equired to visit all his cows according to a tour as described above.
 
 

 

Input

The first line of input contains H and G, separated by a space.
The next H lines contain the xx and yy coordinates of the HH Holsteins, and the next G lines after 
that contain coordinates of the Guernseys. Each coordinate is an integer in the range 0…1000
 

 

Output

Write a single line of output, giving the minimum energy required for FJ‘s tour of all the cows.
 

 

Sample Input

3 2
0 0
1 0
2 0
0 3
1 3

Sample Output

20

HINT

 

Source

 

f[i][j][0/1]表示第一个数组匹配到i 第二个到j 当前在第几个的最小代价 转移见代码

技术分享 
 1 #include<bits/stdc++.h>
 2 #define rep(i,l,r) for(int i=l;i<=r;++i)
 3 using namespace std;
 4 const int N=2015;
 5 struct zs{
 6     int x,y;
 7 }s[N];
 8 typedef long long ll;
 9 int n,m,mp[N][N];
10 ll f[N][N][2];
11 int main(){
12     scanf("%d%d",&n,&m);
13     rep(i,1,n) scanf("%d%d",&s[i].x,&s[i].y);
14     rep(i,1,m) scanf("%d%d",&s[i+n].x,&s[i+n].y);
15     rep(i,1,n+m) rep(j,1,n+m) mp[i][j]=(s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y);
16     rep(i,0,n) rep(j,0,m) rep(k,0,1) f[i][j][k]=1LL<<50;
17     f[1][0][0]=0;
18     rep(i,1,n) rep(j,0,m) {
19         f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+mp[i-1][i],f[i-1][j][1]+mp[n+j][i]));
20         if(j)f[i][j][1]=min(f[i][j][1],min(f[i][j-1][0]+mp[i][n+j],f[i][j-1][1]+mp[n+j-1][n+j]));
21     }
22     printf("%lld\n",f[n][m][0]);
23 }
View Code

 

bzoj4745: [Usaco2016 Dec]Cow Checklist


联系
我们