这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
注意题目有一个很重要的信息:依次找到剩下植株里花生最多的。题目测试数据有点问题,没有输入T。
是一道模拟题把。
题目地址:http://poj.pku.edu.cn/problem/2950/
#include
#include
#include
#include
#include
#include
using namespace std;
int T, M, N, K;
#define MAX_NUM 60
int aField[MAX_NUM][MAX_NUM];
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &M, &N, &K);
for(int i = 1; i <= M; i++)
for(int j = 1; j <= N; j++)
scanf("%d", &aField[i][j]);
int nCuri = 0, nCurj;
int nTotalTime = 0;
int nTotalPeanuts = 0;
while(nTotalTime < K)
{
int maxi, maxj, max = 0;
for(int i = 1; i <= M; i++)
for(int j = 1; j <= N; j++)
if(max < aField[i][j])
{
max = aField[i][j];
maxi = i;
maxj = j;
}
if(max == 0)
break;
//如果当前位置是在路上,
//那么应该走到横坐标nCurj处,再进入花生地
if(nCuri == 0)
nCurj = maxj;
if(nTotalTime + maxi + 1 + abs(maxi - nCuri) + abs(maxj - nCurj) <= K)
//下一行加上走到新位置,以及摘花生的时间
{
nTotalTime += 1 + abs(maxi - nCuri) + abs(maxj - nCurj);
nCuri = maxi;
nCurj = maxj;
nTotalPeanuts += aField[maxi][maxj];
aField[maxi][maxj] = 0;
}
else
break;
}
printf("%d\n", nTotalPeanuts);
}
return 0;
}