花生问题
鲁宾逊先生有一只宠物猴名叫多多。这天他们两个正沿着乡间小路散步突然发现路边的告示牌上贴着一张小小的纸条“欢迎免费品尝我种的花生——熊字”。鲁宾逊先生和多多都很开心因为花生正是他们的最爱。在告示牌背后路边真的有一块花生田花生植株整齐地排列成矩形网格如图1。有经验的多多一眼就能看出每棵花生植株下的花生有多少。为了训练多多的算术鲁宾逊先生说“你先找出花生最多的植株去采摘它的花生然后再找出剩下的植株里花生最多的去采摘它的花生依此类推不过你一定要在我限定的时间内回到路边。”我们假定多多在每个单位时间内可以做下列四件事情中的一件1)从路边跳到最靠近路边即第一行的某棵花生植株2)从一棵植株跳到前后左右与之相邻的另一棵植株3)采摘一棵植株下的花生4)从最靠近路边即第一行的某棵花生植株跳回路边。现在给定一块花生田的大小和花生的分布请问在限定时间内多多最多可以采到多少个花生注意可能只有部分植株下面长有花生假设这些植株下的花生个数各不相同。例如在图2所示的花生田里只有位于(2,5),(3,7),(4,2),(5,4)的植株下长有花生个数分别为13,7,15,9。沿着图示的路线多多在21个单位时间内最多可以采到37个花生。Input输入的第一行包括一个整数T表示数据组数每组输入的第一行包括三个整数M,N和K用空格隔开表示花生田的大小为M*N1<=M,N<=50多多采花生的限定时间为K0<=K<=1000个单位时间。接下来的M行每行包括N个非负整数也用空格隔开第i+1行的第j个整数Pij0<=Pij<=500表示花生田里植株(i,j)下花生的数目0表示该植株下没有花生。Output输出包括T行每一行只包含一个整数即在限定时间内多多最多可以采到花生的个数。SampleInput672100000000000130000000070150000000090000000000SampleOutput37voidhuashengwenti(){intm,n,k,i,j,count=0;intx[400],y[400],value[400],max[400],sign[400];
相关知识
花生问题——百练OJ：2950:摘花生与1928:The Peanuts
【练习赛补题】问题 E: 花生采摘 【模拟】
算法分析实验之采花生遗留数组问题的解决
花生中重金属—镉含量超标问题的试验与研究资源
仓鼠吃多少花生
宠物狗吃花生会有什么影响（了解狗狗吃花生的利弊）
采花生(PAT)
38:花生采摘
花生采摘
文鸟吃花生吗
网址: 花生问题 https://m.mcbbbk.com/newsview691389.html
| 上一篇: 在哪能买到宠物猴？揭阳哪个地方有 |
下一篇: 女子带宠物狗进银行与保安发生争执 |
