首页 > ACM题库 > HDU-杭电 > HDU 1355 The Peanuts-动态规划-[解题报告] C++
2013
12-09

HDU 1355 The Peanuts-动态规划-[解题报告] C++

The Peanuts

问题描述 :

Mr. Robinson and his pet monkey Dodo love peanuts very much. One day while they were having a walk on a country road, Dodo found a sign by the road, pasted with a small piece of paper, saying "Free Peanuts Here! " You can imagine 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.

输入:

The first line of input contains the test case number T (1 <= T <= 20). For each test case, the first line contains three integers, M, N and K (1 <= M, N <= 50, 0 <= K <= 20000). Each of the following M lines contain N integers. None 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.

输出:

For each test case, print one line containing the amount of peanuts Dodo can pick.

样例输入:

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

#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";
        }
    }
}

解题报告转自:http://blog.csdn.net/nealgavin/article/details/8552197


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。