The Peanuts
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 313 Accepted Submission(s): 174
how happy Mr. Robinson and Dodo were.
There was a peanut field on one side of the road. The peanuts were planted on the intersecting points of a grid as shown in Figure-1. At each point, there are either zero or more peanuts. For example, in Figure-2, only four points have more than zero peanuts,
and the numbers are 15, 13, 9 and 7 respectively. One could only walk from an intersection point to one of the four adjacent points, taking one unit of time. It also takes one unit of time to do one of the following: to walk from the road to the field, to
walk from the field to the road, or pick peanuts on a point.
According to Mr. Robinson's requirement, Dodo should go to the plant with the most peanuts first. After picking them, he should then go to the next plant with the most peanuts, and so on. Mr. Robinson was not so patient as to wait for Dodo to pick all the peanuts
and he asked Dodo to return to the road in a certain period of time. For example, Dodo could pick 37 peanuts within 21 units of time in the situation given in Figure-2.
Your task is, given the distribution of the peanuts and a certain period of time, tell how many peanuts Dodo could pick. You can assume that each point contains a different amount of peanuts, except 0, which may appear more than once.
of the integers will exceed 3000. (M * N) describes the peanut field. The j-th integer X in the i-th line means there are X peanuts on the point (i, j). K means Dodo must return to the road in K units of time.
2 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 6 7 20 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0
37 28
思路:先从大到小排序,找到取花生的顺序,然后依次判断取下一个花生是否能在时间内顺利出去。
杭电将这题归为DP,那我也这么办吧。
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int mm=55; class node { public: int x,y,peanuts; }f[mm*mm]; int grap[mm][mm]; int dp[2][mm*mm]; int cas,m,n,t,pos; bool cmp(node a,node b) { return a.peanuts>b.peanuts; } int fabs(int x) { return x>0?x:-x; } int main() { while(cin>>cas) { while(cas--) { pos=0; cin>>m>>n>>t; memset(dp,0,sizeof(dp)); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { cin>>grap[i][j]; f[pos].x=i;f[pos].y=j;f[pos].peanuts=grap[i][j]; pos++; } sort(f,f+pos,cmp); int shu=f[0].peanuts,uset=0,ans=0,nx=0,ny=f[0].y; for(int i=0;i<pos;i++) { if(f[i].peanuts==0)break; if(uset+fabs(f[i].x-nx)+fabs(f[i].y-ny)+f[i].x+1<=t) { uset+=fabs(f[i].x-nx)+fabs(f[i].y-ny)+1; nx=f[i].x;ny=f[i].y; ans+=f[i].peanuts; } else break; } cout<<ans<<"\n"; } } }