Picking Coins Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB Problem description A pack of coins have been divided into piles, each pile has some number Ni (1 <= Ni <= 25) of coins. All the piles have been placed in an area of R rows(1 <= R <= 100) and C columns (1 <= C <= 100).Given a starting location, you have to make your way out of the area and gather as many coins as you can. From the position (r,c) you can only move to (r-1,c+1), (r, c+1), or (r+1,c+1) and endup your way at any edge of the area. If there exist more than one path that can gather the maximum number of coins, make your path the shortest. Input There will be only one testcase in the input file, the first line contains Two space-separated integers, respectively R and C, then followed R lines, Each line contains C space-separated integers in the obvious order, the last few lines each contains two integer which indicate the starting location. Output For each starting location, output the maximum number of coins you could get and the total length of your path in a single line. Sample Input 3 7 1 2 6 7 0 0 0 3 5 8 0 0 0 0 4 9 0 0 0 0 0 1 1 3 1 3 6 Sample Output 21 4 28 4 0 1 Judge Tips end / start-> 1 2 6 7 0 0 0 \ / 3 5-8 0 0 0 0 4 9 0 0 0 0 0 The path above yields 1 + 5 + 8 + 7 = 21 coins, the length of path is 4 解题思路: 知道 DP 的人首先就会想到DP, 这里我就是用 DP的, 注意特殊数据 3 70 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 01 12 13 23 6 输出为: 0 10 20 10 1 ///// code 2008-4-28 #include <iostream>#include <queue>using namespace std; const int MAX = 100;struct t_node{    int sum;    int len;    bool bInQue;    t_node& operator =(const t_node &other){         sum = other.sum;        len = other.len;        return *this;    }}; struct t_queue_node{    int x;    int y;    int len;    t_queue_node(int py=0, int px=0, int plen=1){ y=py; x=px; len=plen; }}; t_node g_node[MAX][MAX], g_best; void init_node(int r, int c){    for(int i=0; i<r; i++){        for(int j=0; j<c; j++){            g_node[i][j].sum = 0;            g_node[i][j].len = INT_MAX;            g_node[i][j].bInQue = false;        }    }} void update(int sx, int sy, int dx, int dy, int len, int pile[][MAX],             queue<t_queue_node> &qu){    if( !g_node[dy][dx].bInQue ){        qu.push(t_queue_node(dy, dx, len+1));        g_node[dy][dx].bInQue = true;    }     if( (g_node[sy][sx].sum+pile[dy][dx]>g_node[dy][dx].sum) ||        (g_node[sy][sx].sum+pile[dy][dx]==g_node[dy][dx].sum &&         g_node[sy][sx].len+1<g_node[dy][dx].len) ){        g_node[dy][dx].len = g_node[sy][sx].len+1;        g_node[dy][dx].sum = g_node[sy][sx].sum+pile[dy][dx];    }} int main(){    int pile[MAX][MAX];    int sx,sy,c,r;        scanf("%d %d",&r,&c);    for(int i=0; i<r; i++){        for(int j=0; j<c; j++)            scanf("%d",&pile[i][j]);    }     while(scanf("%d %d",&sy,&sx)!=EOF){        init_node(r, c);        sx--;        sy--;        queue<t_queue_node> que;        g_node[sy][sx].len = 1;        g_node[sy][sx].sum = pile[sy][sx];        g_node[sy][sx].bInQue = true;        que.push(t_queue_node(sy, sx, 2));         g_best.len = INT_MAX;        g_best.sum = INT_MIN;         t_queue_node tp;        for(bool bEnd; que.size()!=0; ){            tp = que.front();            que.pop();            bEnd = false;             if(tp.x+1<c && tp.y-1>=0)                 update(tp.x, tp.y, tp.x+1, tp.y-1, tp.len, pile, que);            else                 bEnd = true;             if(tp.x+1<c)                 update(tp.x, tp.y, tp.x+1, tp.y, tp.len, pile, que);            else                 bEnd = true;             if(tp.x+1<c && tp.y+1<r)                 update(tp.x, tp.y, tp.x+1, tp.y+1, tp.len, pile, que);            else                 bEnd = true;             if( bEnd && (g_node[tp.y][tp.x].sum>g_best.sum ||                (g_node[tp.y][tp.x].sum==g_best.sum &&                 g_node[tp.y][tp.x].len<g_best.len)) )                g_best = g_node[tp.y][tp.x];        }        printf("%d %d\n", g_best.sum, g_best.len);    }    return 0;}

评论