首页 > 代码库 > USACO月赛—JAN12 Silver
USACO月赛—JAN12 Silver
题目描述After several years of record milk production, Farmer John now operates an entire network of N farms (1 <= N <= 100). Farm i is located at position (x_i, y_i) in the 2D plane, distinct from all other farms, with both x_i and y_i being integers.FJ needs your help planning his daily delivery route to bring supplies to the N farms. Starting from farm 1, he plans to visit the farms sequentially (farm 1, then farm 2, then farm 3, etc.), finally returning to farm 1 after visiting farm N. It tames FJ one minute to make a single step either north, south, east, or west. Furthermore, FJ wants to visit each farm exactly once during his entire journey (except farm 1, which he visits twice of course). Please help FJ determine the minimum amount of time it will take him to complete his entire delivery route.输入* Line 1: The number of farms, N.* Lines 2..1+N: Line i+1 contains two space-separated integers, x_i and y_i (1 <= x_i, y_i <= 1,000,000).输出* Line 1: The minimum number of minutes FJ needs to complete his delivery route, or -1 if it is impossible to find a feasible delivery route that visits every farm exactly once (except farm 1).样例输入42 22 42 11 3样例输出12提示OUTPUT DETAILS:FJ can complete his delivery route in 12 minutes: 2 minutes to go from farm 1 to farm 2, 5 minutes to go from farm 2 to farm 3 (circumventing farm 1), 3 minutes to go from farm 3 to farm 4, and then 2 minutes to return to farm 1.
做法:把每个点的四周的四个点拆出来(显然如果最短路径则不经过该点必经过四周的点),然后做n次最短路径即可。。但中间细节比较多,写的时候要注意。
这题是个不错的最短路径题,比之前每次都做模板题好多了T_T...不过考试的时候没做出来。。果然还是太水了TTTTTT_______TTTTTT...
题目描述Farmer John has just received a new shipment of N (1 <= N <= 20) bales of hay, where bale i has size S_i (1 <= S_i <= 100). He wants to divide the bales between his three barns as fairly as possible. After some careful thought, FJ decides that a "fair" division of the hay bales should make the largest share as small as possible. That is, if B_1, B_2, and B_3 are the total sizes of all the bales placed in barns 1, 2, and 3, respectively (where B_1 >= B_2 >= B_3), then FJ wants to make B_1 as small as possible.For example, if there are 8 bales in these sizes:2 4 5 8 9 14 15 20A fair solution isBarn 1: 2 9 15 B_1 = 26Barn 2: 4 8 14 B_2 = 26Barn 3: 5 20 B_3 = 25Please help FJ determine the value of B_1 for a fair division of the hay bales.输入* Line 1: The number of bales, N.* Lines 2..1+N: Line i+1 contains S_i, the size of the ith bale.输出* Line 1: Please output the value of B_1 in a fair division of the hay bales.样例输入814251589204样例输出26
做法:水dp,和三角形牧场差不多,f(i,j)表示i,j是否可以构成。
题目描述Farmer John has discovered that his cows produce higher quality milk when they are subject to strenuous exercise. He therefore decides to send his N cows (1 <= N <= 25,000) to climb up and then back down a nearby mountain!Cow i takes U(i) time to climb up the mountain and then D(i) time to climb down the mountain. Being domesticated cows, each cow needs the help of a farmer for each leg of the climb, but due to the poor economy, there are only two farmers available, Farmer John and his cousin Farmer Don. FJ plans to guide cows for the upward climb, and FD will then guide the cows for the downward climb. Since every cow needs a guide, and there is only one farmer for each part of the voyage, at most one cow may be climbing upward at any point in time (assisted by FJ), and at most one cow may be climbing down at any point in time (assisted by FD). A group of cows may temporarily accumulate at the top of the mountain if they climb up and then need to wait for FD‘s assistance before climbing down. Cows may climb down in a different order than they climbed up.Please determine the least possible amount of time for all N cows to make the entire journey.输入* Line 1: The number of cows, N.* Lines 2..1+N: Line i+1 contains two space-separated integers: U(i) and D(i). (1 <= U(i), D(i) <= 50,000).输出* Line 1: A single integer representing the least amount of time for all the cows to cross the mountain.样例输入36 48 12 3样例输出17提示OUTPUT DETAILS:If cow 3 goes first, then cow 1, and then cow 2 (and this same order is used for both the ascent and descent), this gives a total time of 17.
做法:贪心,每次保证上坡小的尽量在前,下坡小的尽量在后,中间分四种情况讨论下即可。。具体严谨证明偶也不会。。先挖坑QAQ..
Codes:
1 #include<set> 2 #include<queue> 3 #include<vector> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<iostream> 8 #include<algorithm> 9 const int N = 110; 10 using namespace std; 11 const int limits = 1000000; 12 typedef pair<int,int> Points; 13 const int dx[5] = {0,0,1,-1,0}, 14 dy[5] = {0,1,0,0,-1}; 15 #define x first 16 #define y second 17 #define clr(a,b) memset(a,b,sizeof(a)) 18 #define For(i,n) for(int i=1;i<=n;i++) 19 #define Rep(i,l,r) for(int i=l;i<=r;i++) 20 #define Swap(A,B) {Points T = A ; A = T; T = B;} 21 int n,npcnt,es,stack[5*N],head[N*5],dis[5*N],ans; 22 set<Points> hash,farm; 23 bool vis[5*N]; 24 Points p[N],np[5*N]; 25 struct edge{ 26 int t,next,w; 27 }E[5*N*5*N]; 28 29 int Len(Points A,Points B){ 30 return abs(B.x-A.x)+abs(B.y-A.y); 31 } 32 33 void makelist(int s,int t){ 34 E[es].t = t; E[es].next = head[s];E[es].w = Len(np[s],np[t]); 35 head[s] = es++; 36 } 37 38 bool inseg(Points out,Points A,Points B){ 39 if(A.x==B.x) 40 if(min(A.y,B.y)<out.y&&out.y<max(A.y,B.y)&&out.x==A.x) return true; 41 if(A.y==B.y) 42 if(min(A.x,B.x)<out.x&&out.x<max(A.x,B.x)&&out.y==A.y) return true; 43 return false; 44 } 45 46 bool check(Points A,Points B){ 47 Points C;// _| 48 if(A.x>B.x) Swap(A,B); 49 C.y = A.y; C.x = B.x; 50 bool Flag = A.x==B.x||A.y==B.y||farm.find(C)==farm.end(); 51 For(i,n) 52 if(inseg(p[i],A,C)||inseg(p[i],C,B)){ 53 Flag = false; 54 break; 55 } 56 if(Flag) return true; 57 C.x = A.x; C.y = B.y; 58 Flag = A.x==B.x||A.y==B.y||farm.find(C)==farm.end(); 59 For(i,n) 60 if(inseg(p[i],A,C)||inseg(p[i],C,B)){ 61 Flag = false; 62 break; 63 } 64 return Flag; 65 } 66 67 void init(){ 68 scanf("%d",&n); 69 For(i,n) { 70 scanf("%d%d",&p[i].y,&p[i].x); 71 hash.insert(p[i]);farm.insert(p[i]); 72 np[i] = p[i]; 73 }npcnt = n; 74 clr(head,-1); 75 For(i,n) 76 For(j,4){ 77 int newx = p[i].x + dx[j] , newy = p[i].y + dy[j]; 78 if(newx<1||newx>limits||newy<1||newy>limits) continue; 79 if(hash.find(make_pair(newx,newy))==hash.end()) {np[++npcnt] = make_pair(newx,newy);hash.insert(make_pair(newx,newy));} 80 } 81 For(i,npcnt-1) 82 Rep(j,i+1,npcnt){ 83 if(check(np[i],np[j])) { 84 makelist(i,j); 85 makelist(j,i); 86 } 87 } 88 } 89 90 int SPFA(int s,int t){ 91 For(i,5*n) dis[i] = 214748364; 92 memset(vis,0,sizeof(vis)); 93 dis[s] = 0; 94 stack[stack[0]=1,1] = s; 95 while(stack[0]){ 96 int First = stack[stack[0]--];vis[First] = false; 97 for(int p=head[First];p!=-1;p=E[p].next){ 98 int v = E[p].t; 99 if(v<=n&&v!=s&&v!=t) continue;100 if(dis[First]+E[p].w<dis[v]) {101 dis[v] = dis[First] + E[p].w;102 if(!vis[v]) {vis[v] = true; stack[++stack[0]] = v;}103 } 104 } 105 }106 return dis[t];107 }108 109 void Work(){110 For(i,n){111 int W = SPFA(i,(i==n)?(1):(i+1)); 112 if(W>21474836) puts("-1");113 if(W>21474836) return;114 ans+=W;115 }116 printf("%d\n",ans);117 } 118 119 int main(){120 // freopen("date.in","r",stdin);121 // freopen("date.out","w",stdout);122 init();123 Work();124 return 0;125 }126 --------------------------------------A题--------------------------------------127 #include<queue>128 #include<cstdio>129 #include<cstdlib>130 #include<cstring>131 #include<iostream>132 #include<algorithm>133 using namespace std;134 const int N = 30;135 const int MAXS = 20*100/3;136 #define For(i,n) for(int i=1;i<=n;++i)137 #define Rep(i,l,r) for(int i=l;i<=r;++i)138 139 int A[N],f[N][MAXS+200][MAXS+200],sum,ans=2147483647,n;140 141 int main(){142 scanf("%d",&n);143 For(i,n) {scanf("%d",&A[i]),sum+=A[i];};144 memset(f,false,sizeof(f));145 f[0][0][0] = true;146 For(i,n){147 Rep(j,0,MAXS)148 Rep(k,0,MAXS) 149 if(f[i-1][j][k]){150 f[i][j][k] = true;151 f[i][j+A[i]][k] = true;152 f[i][j][k+A[i]] = true;153 }154 }155 For(i,MAXS){156 For(j,MAXS)157 if(f[n][i][j])158 ans = min(ans,max(i,max(j,sum-i-j)));159 }160 printf("%d\n",ans);161 return 0;162 }163 --------------------------------------B题--------------------------------------164 #include<queue>165 #include<cstdio>166 #include<iostream>167 #include<algorithm>168 using namespace std;169 const int N = 25100;170 #define Points pair<int,int>171 #define For(i,n) for(int i=1;i<=n;++i)172 #define Rep(i,l,r) for(int i=l;i<=r;++i)173 174 Points A[N];175 int n;176 177 bool cmp(Points A,Points B){178 if(A.first<A.second){179 if(B.first<B.second) return A.first<B.first;180 else return true;181 }else{182 if(B.first>B.second) return A.second>B.second;183 else return false;184 } 185 }186 187 void solve(){188 sort(A+1,A+n+1,cmp);189 int sum1 = 0 ,sum2 = A[1].first;190 For(i,n){191 sum1+=A[i].first;192 sum2=max(sum1,sum2)+A[i].second;193 }194 printf("%d\n",sum2);195 }196 197 int main(){198 scanf("%d",&n);199 For(i,n) scanf("%d%d",&A[i].first,&A[i].second);200 solve();201 return 0;202 }203 ----------------------------------C题------------------------------------------
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。