PKU-1928:The Peanuts

keyword

シミュレーション　C++

問題概要

M*N(M,N<50)のセル内に価値vのピーナッツが埋まっている。猿が価値の高い順にピーナッツを拾う。時刻T以内に戻ってこなければならない。猿は最大でいくつ分の価値のピーナッツを拾えるか求める問題。

解法

価値の高いものから拾いにいく。次の価値の高いものを拾いに行ってそれから戻ってこられるなら次のを取りにいく。そうでないならその時点で戻る、とすればよい。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_W = 55;

struct node{
    int y, x, value;
    node(int _v, int _y, int _x):value(_v), y(_y), x(_x){}
    node(){ node(0,0,0); }
};

bool operator<(const node& a, const node& b){ return a.value > b.value; }

node ns[MAX_W*MAX_W];
int W, H, K, p;

int solve(){
    if(!p) return 0;
    sort(ns, ns+p);
    int x=ns[0].x, y=0, i=0, t=0, ret = 0;
    while(1){
        int d = abs(x-ns[i].x) + abs(y-ns[i].y);
        if(t + d + 1 + ns[i].y <= K){
            x = ns[i].x;
            y = ns[i].y;
            ret += ns[i].value;
            t += d + 1;
            if(++i == p) break;
        }
        else break;
    }
    return ret;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&H,&W,&K);
        p = 0;
        for(int i=1; i<=H; i++)for(int j=1; j<=W; j++){
            int v;
            scanf("%d",&v);
            if(v>0){
                ns[p++] = node(v,i,j);
            }
        }
        printf("%d\n",solve());
    }
    return 0;
}